atkin实现中的5的c++倍数

Question

我正在欧拉项目中解决一个问题，该问题要求我找到200万以下所有素数的和。我试着实现atkin的筛，奇怪的是，它把65，85这样的数字设置为素数。我看了一天多的代码和算法，但没有发现任何错误。我肯定是什么傻事，但我找不到。提前谢谢我正在使用visualstudioexpress2012。

这是代码：

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
#include <conio.h>
 int main(){
    long long int limit,n;
    std::cout<<"Enter a number...."<<std::endl;
    std::cin>>limit;
    std::vector<bool> prime; 

    for(long long int k=0;k<limit;k++){ //sets all entries in the vector 'prime' to false
        prime.push_back(false);
    }
    long long int root_limit= ceil(sqrt(limit));
    //sive of atkin implementation
    for(long long int x=1;x<=root_limit;x++){
        for(long long int y=1;y<=root_limit;y++){
            n=(4*x*x)+(y*y);
            if(n<=limit && (n%12==1 || n%12==5)){
                prime[n]=true;
            }
            n=(3*x*x)+(y*y);
            if(n<=limit && n%12==7){
                prime[n]=true;
            }
            n=(3*x*x)-(y*y);
            if(x>y && n<=limit && n%12==11){
                prime[n]=true;
            }
        }
    }

    //loop to eliminate squares of the primes(making them square free)
    for(long long int i=5;i<=root_limit;i++){
        if(prime[i]==true){
            for(long long int j=i*i;j<limit;j+=(i*i)){
                prime[j]=false;
            }
        }
    }
    unsigned long long int sum=0;
    //print values to a seperate text file 
    std::ofstream outputfile("data.txt");
    outputfile<<"2"<<std::endl;
    outputfile<<"3"<<std::endl;
    for(long long int l=5;l<limit;l++){
        if(prime[l]==true){
            sum+=l;
            outputfile<<l<<std::endl;;
        }
    }
    outputfile.close();

    std::cout<<"The sum is...."<<sum+5<<std::endl;
    prime.clear();
    return 0;
}

和她的数据.txt我指出了几个错误

23.5.7.111317192329313741434753596165&lt-----677173798385&lt-----899197101103107109113127131137139143145&lt----149151157163167173179181185&lt----19119319719920521122122322722923323924124725125725926326526927127728128329329930530731131331733133734734935335936536737337737938338939740140340740941942142743143343944344544945746146346747948148548749149349950350550951152152353354154554755755956356556957157758759359960160761161361761962963164164364765365966167167367767968368568969169770170370971972773373974374575175776176376776977378578779379780380981182182382782983985185385785986386587187788188388790190590791191992392993794194794995396596797197798398599199710091013101910211027103110331037103910491051106110631067106910731079108710911093109710991103110511091117112311291145114711511153115711591163116511711181118711891193119912011205121312171223122912311237124112491259126112671277127912831285128912911297130113031307131313191321132713391345135113611367137313811385138713911399140314051409141714231427142914331439144714511453145914651469147114811483148714891493149915111513151715231531153715431549155315591565156715711579158315851591159716011603160716091613161916211627163716491651165716631667166916791685168716931697169917031709171717211723172717331739174117451747175317591765176917771781178317871789180118071811182318311843184718531861186518671871187318771879188518891891190119071913192119311933193719391945194919511961196319731979198519871991199319971999

Answer 1

您应该将条目翻转到筛选列表中。在第一个嵌套的for循环而不是prime[n]=true;中，应该有prime[n]=!prime[n];