0

我在 C++ 中实现了 Atkin 的 Sieve 以返回 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、

我究竟做错了什么 ？

4

0 回答 0