Недавно я очень заинтересовался простыми числами и попытался написать программы для их вычисления. Я смог сделать сито из программы Sundaram, которая вычисляла миллион простых чисел за пару секунд. Я считаю, что это довольно быстро, но я хотел лучше. Затем я попытался создать решето Аткина. Я собрал рабочий код C++ за 20 минут. после копирования псевдокода из Википедии.
Я знал, что он не будет идеальным, потому что в конце концов это псевдокод. Я ожидал, по крайней мере, лучших времен, чем мое сито Sundaram, но я был так неправ. Это очень очень медленно. Я просматривал его много раз, но не нашел существенных изменений, которые можно было бы внести. Глядя на мой код, помните, я знаю, что он неэффективен, я знаю, что использовал системные команды, я знаю, что это повсюду, но это не проект или что-то важное, это для меня.
#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;
}
float
вместоlimit
иslimit
? - person Retired Ninja   schedule 04.01.2014