作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我最近对素数很感兴趣,并尝试编写程序来计算它们。我能够制作一个 Sundaram 程序的筛子,该程序能够在几秒钟内计算出一百万个素数。我相信这相当快,但我想要更好的。我继续尝试制作 Sieve of Atkin ,从维基百科复制伪代码后,我在 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;
}
最佳答案
这不完全是一个答案(IMO,您已经在评论中得到了答案),而是一个用于比较的快速标准。 Eratosthenes 筛法应该在相当现代的机器上好在一秒钟内找到一百万个素数。
#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
显然,速度会因处理器、时钟速度等因素而有所不同,但对于任何合理现代的东西,我仍然希望时间少于一秒。当然,如果您决定将素数写到一个文件中,您可以预期会增加一些时间,但即使这样我也希望总时间不到一秒——我的笔记本电脑的硬盘驱动器相对较慢,写出来这些数字总共只需要大约 0.6 秒。
关于c++ - 阿特金筛法出奇地慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20917675/
我是一名优秀的程序员,十分优秀!