Я реализовал Sieve of Atkin в C ++ для возврата вектора типа bool, но он не помечает некоторые простые числа.
// Example program
#include <iostream>
#include <vector>
std::vector<bool> listPrimes(int limit){
std::vector<bool> primes(limit);
primes[2] = primes[3] = true;
for(int i=1; i*i < limit; ++i){
for(int j=1; j*j < limit; ++j){
int n = (4*i*i) + (j*j);
if (n <= limit && (n % 12 == 0 || n % 12 == 5 ))
primes[n] = !primes[n];
n = (3*i*i) + (j*j);
if (n <= limit && n % 12 == 7 )
primes[n] = !primes[n];
n = (3*i*i) - (j*j);
if ( i > j && n <= limit && n % 12 == 11 )
primes[n] = !primes[n];
}
}
for(int i=5; i*i < limit; ++i ){
if(primes[i])
for(int j=i*i; j < limit; j+=i*i)
primes[i] = false;
}
return primes;
}
int main()
{
std::vector<bool> primes = listPrimes(100);
for(int i=0; i < 100; ++i)
if(primes[i])
std::cout << i << ", ";
return 0;
}
Вот вывод данного кода.
2, 3, 11, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 67, 71, 72, 79, 83, 89,
Что я делаю неправильно ?
Задача ещё не решена.
Других решений пока нет …