0

我最近对素数非常感兴趣，并尝试编写程序来计算它们。我能够筛选出能够在几秒钟内计算出一百万个素数的 Sundaram 程序。我相信这很快，但我想要更好。我继续尝试制作一个阿特金筛子，在从 Wikipedia 复制伪代码后，我在 20 分钟内将工作 C++ 代码拼凑在一起。

我知道它并不完美，因为毕竟它的伪代码。虽然我期待至少比我的 Sundaram Sieve 更好，但我错了。它非常非常慢。我已经看过很多次了，但我找不到任何可以做出的重大改变。查看我的代码时，请记住，我知道它效率低下，我知道我使用了系统命令，我知道它无处不在，但这不是一个项目或任何重要的东西，它是为我准备的。

#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;
}
4

2 回答 2

2

这不完全是一个答案（IMO，你已经在评论中得到了答案），而是一个快速的比较标准。在一台相当现代的机器上，埃拉托色尼的筛子应该在一秒钟内找到一百万个素数。

#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;
}

在我的笔记本电脑上运行它，我得到以下结果：

Total primes: 1000000
Time: 0.106 seconds

显然，速度会随着处理器、时钟速度等的不同而有所不同，但是对于任何相当现代的东西，我仍然期望不到一秒的时间。当然，如果您决定将质数写入文件，您可以期望这会增加一些时间，但即便如此，我预计总时间会在 1 秒以下——我的笔记本电脑的硬盘驱动器相对较慢，写出这些数字只能使总数达到约 0.6 秒。

于 2014-01-04T06:50:02.700 回答
0

矢量是一个位集。更新不在缓存中的位集值是昂贵的。试试vector，写入要便宜得多。

于 2014-01-04T21:01:49.690 回答