素数の処理で恐ろしい間違いを犯していたのだが、速度にはそれほど影響がなかった。遅いのは素数の生成の部分だったが、本質的に速くなりそうになかった。Pythonでリストを使うと非常に遅くなることはなんとなく分かっていたので、C++でvectorを使ってほとんど同じコードを書いてみた。
80倍以上速くなった。こうも違うとなんらかの対策が必要かもしれない。
（追記）
C++でなんの工夫もなしに全部書いたら24sだった。
#include
#includeusing namespace std;
class cGenPrimes {
vectorprimes;
vectora;
static const int max_p = 100000;
static const int sieve_size = 100000;
int s, e;
int pos;
public:
cGenPrimes() {
make_primes();
a.resize(sieve_size + 1);
s = 1;
e = sieve_size + 1;
sieve();
pos = 1;
}
int operator()() {
while(true) {
pos++;
if(pos > sieve_size) {
new_sieve();
pos = 1;
}
if(a[pos])
return s + pos - 1;
}
}
void new_sieve() {
s += sieve_size;
e += sieve_size;
sieve();
}
void sieve() {
fill(a.begin(), a.end(), 1);
typedef vector::const_iterator CIT;
for(CIT q = primes.begin(); q != primes.end(); ++q) {
int p = *q;
if(p * p >= e)
break;
for(int k = (s + p - 1) / p * p; k < e; k += p) {
if(k == p)
continue;
a[k-s+1] = 0;
}
}
}
bool is_prime(int n) {
typedef vector::const_iterator CIT;
for(CIT q = primes.begin(); q != primes.end(); ++q) {
int p = *q;
if(p * p > n)
return true;
else if(n % p == 0)
return false;
}
return true;
}
void make_primes() {
primes.push_back(2);
for(int n = 3; n <= max_p; n += 2) {
if(is_prime(n))
primes.push_back(n);
}
}
};class cGenTriplePair {
cGenPrimes gen_primes;
int counter;
int prev_p;
public:
cGenTriplePair() {
counter = 0;
prev_p = 1;
}
int operator()() {
while(true) {
int p = gen_primes();
int tmp = prev_p;
prev_p = p;
if(p - tmp == 6) {
counter++;
if(counter >= 3)
return p - 9;
}
else {
counter = 0;
}
}
}
};int main() {
cGenTriplePair gen;
int counter = 0;
while(true) {
int n = gen();
counter++;
if(n > (int)1e8)
break;
}
cout << counter << endl;
}
