阿特金筛子出奇的慢 [英] Sieve Of Atkin is surprisingly slow

问题描述

我最近对质数非常感兴趣，并尝试制作程序来计算它们.我能够筛选出Sundaram程序，该程序能够在几秒钟内计算出一百万个质数.我相信那是非常快的，但是我想要更好.我继续尝试制作阿特金筛子，我在20分钟内拍了拍可工作的C ++代码从Wikipedia复制伪代码后.

I recently became very interested in prime numbers and tried making programs to calculate them. I was able to make a sieve of Sundaram program that was able to calculate a million prime numbers in a couple seconds. I believe that's pretty fast, but I wanted better. I went on to try to make a Sieve of Atkin, I slapped together working C++ code in 20 minutes after copying the pseudocode from Wikipedia.

我知道它不是完美的，因为毕竟它是伪代码.虽然我期望至少比我的Sundaram筛筛机更好，但是我错了.这非常非常慢.我已经看了很多遍了，但是我找不到可以进行的任何重大更改.在查看我的代码时，请记住，我知道它效率低下，我知道我使用了系统命令，我知道它无处不在，但这不是项目，也不重要，这是对我有用的.

I knew that it wouldn't be perfect because after all, its pseudocode. I was expecting at least better times than my Sundaram Sieve though, but I was so wrong. It's very very slow. I have looked it over many times but I cannot find any significant changes that could be made. When looking at my code remember, I know it's inefficient, I know I used system commands, I know it's all over the place, but this isn't a project or anything important, it's for me.

#include <iostream>
#include <fstream>
#include <time.h>
#include <Windows.h>
#include <vector>

using namespace std;

int main(){

float limit;
float slimit;
long int n;
int counter = 0;
int squarenum;
int starttime;
int endtime;
vector <bool> primes;

ofstream save;
save.open("primes.txt");
save.clear();

cout << "Find all primes up to: " << endl;
cin >> limit;

slimit = sqrt(limit);

primes.resize(limit);

starttime = time(0);

// sets all values to false
for (int i = 0; i < limit; i++){

    primes[i] = false;
}


//puts in possible primes
for (int x = 1; x <= slimit; x++){

    for (int y = 1; y <= slimit; y++){


        n = (4*x*x) + (y*y);
        if (n <= limit && (n%12 == 1 || n%12 == 5)){

            primes[n] = !primes[n];
        }

        n = (3*x*x) + (y*y);
        if (n <= limit && n% 12 == 7){

            primes[n] = !primes[n];
        }

        n = (3*x*x) - (y*y);
        if ( x > y && n <= limit && n%12 == 11){

            primes[n] = !primes[n];
        }
    }
}

//square number mark all multiples not prime

for (float i = 5; i < slimit; i++){

    if (primes[i] == true){

        for (long int k = i*i; k < limit; k = k + (i*i)){

            primes[k] = false;
        }
    }
}

endtime = time(0);
cout << endl << "Calculations complete, saving in text document" << endl;


// loads to document
for (int i = 0 ; i < limit ; i++){

    if (primes[i] == true){


        save << counter << ") " << i << endl;
        counter++;
    }
}

save << "Found in " << endtime - starttime << " seconds" << endl;

save.close();

system("primes.txt");

system ("Pause");
return 0;
}

推荐答案

这并不完全是答案(IMO，您已经在注释中得到了答案)，但是是比较的快速标准.在适当合理的现代机器上，一秒钟的Eratosthenes筛子应该在井中找到一百万个素数.

This isn't exactly an answer (IMO, you've already gotten an answer in the comments), but a quick standard for comparison. A sieve of Eratosthenes should find a million primes in well under a second on a reasonably modern machine.

#include <vector>
#include <iostream>
#include <time.h>

unsigned long primes = 0;

int main() {
    // empirically derived limit to get 1,000,000 primes
    int number = 15485865; 

    clock_t start = clock();
    std::vector<bool> sieve(number,false);
    sieve[0] = sieve[1] = true;

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            ++primes;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    clock_t stop = clock();

    std::cout.imbue(std::locale(""));
    std::cout << "Total primes: " << primes << "\n";
    std::cout << "Time: " << double(stop - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

在笔记本电脑上运行它，结果是:

Running this on my laptop, I get a result of:

Total primes: 1000000
Time: 0.106 seconds

很明显，速度会随处理器，时钟速度等的不同而变化，但是对于合理来说，我仍然希望时间少于一秒钟.当然，如果您决定将素数写入文件中，则可以预期会花费一些时间，但是即使如此，我仍然希望总时间不到一秒钟-使用笔记本电脑相对较慢的硬盘驱动器，即可写入这些数字最多只能使总数达到约0.6秒.

Obviously, speed will vary somewhat with processor, clock speed, etc., but with anything reasonably modern, I'd still expect a time of less than a second. Of course, if you decide to write the primes out to a file, you can expect that to add some time, but even with that I'd expect a total time under a second--with my laptop's relatively slow hard drive, writing out the numbers only gets the total up to about 0.6 seconds.

这篇关于阿特金筛子出奇的慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！