[交流] Euler 工程 第三十五题：循环质数 已有4人参与

# Euler Project Problem 35
#

# Gen a prime list
oneMillion = 1000000
primes = range(2, oneMillion+1);

for x in primes:
    if x > 0:
        for n in xrange(2*x, oneMillion+1, x):
            primes[n-2] = 0

primes = [x for x in primes if x > 0]


primes = set(primes)
# Count
count = 0
for n in primes:
    s = str(n)
    flag = True
    for x in xrange(len(s)):
        s = s[1:] + s[0]
        if int(s) not in primes:
            flag = False
            break
    if flag:
        count += 1
        print n
print "Total", count

Total 55

real        0m1.244s
user        0m1.200s
sys        0m0.040s

#include
#include

using namespace std;

void primesLessThan(int n, vector& v) {
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) continue;

        for(int j = 2*i; j <= n; j += i) {
            if(v[j] == 0) continue;

            v[j] = 0;
        }
    }
}

bool checkRotation(int n, const vector& v) {
    if (n < 10) return true;

    int len = 0, pow = 1;

    for(int tmp = n; tmp > 0; tmp /= 10) {
        len += 1;
        pow *= 10;
    }
    pow /= 10;

    int tmp = n;

    for(int i = 0; i < len - 1; i++) {
        int lastDigit = tmp % 10;
        tmp /= 10;
        tmp += lastDigit * pow;
        if(v[tmp] == 0) {
            return false;
        }
    }
    return true;
}

int main(int argc, char ** argv) {
    int oneMillion = 1000000;
    int oneHundred = 100;
    vector primes(oneMillion+1, 1);
    primesLessThan(oneMillion, primes);

    int count = 0;
    for(int i = 2; i < oneMillion; i++) {
        if(primes[i] == 0) continue;

        if (checkRotation(i, primes)) {
            count += 1;
        }
    }

    cout<<"Total:"< }

Originally posted by tieer at 2011-07-07 09:59:28:
菜鸟正在学习Python，不知道楼上能不能方便给语句写个解释，以便拜读，呵呵，谢谢啊