Сито Аткин на удивление медленно

Question

Сито Аткин на удивление медленно

Недавно я очень заинтересовался простыми числами и пытался создавать программы для их вычисления. Мне удалось создать сито из программы «Сундарам», которая могла вычислить миллион простых чисел за пару секунд. Я считаю, что это довольно быстро, но я хотел лучшего. Я попытался сделать Сито Аткина, Я собрал вместе работающий код C ++ через 20 минут после копирования псевдокода из Википедии.

Я знал, что это не было бы идеально, потому что, в конце концов, его псевдокод. Я ожидал, по крайней мере, лучших времен, чем мое Сито Сундарам, но я был так неправ. Это очень очень медленно. Я просматривал это много раз, но не могу найти каких-либо существенных изменений, которые могли бы быть сделаны. Глядя на мой код, помните, я знаю, что он неэффективен, я знаю, что использовал системные команды, я знаю, что это повсеместно, но это не проект или что-то важное, это для меня.

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

0

c++optimization performance sieve

Решение

Другие решения

вектор является битовым. Обновление значений набора битов, которых нет в кэше, обходится дорого. Попробуйте вектор, гораздо дешевле написать.

0

Источник

Accepted Answer

Это не совсем ответ (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

Очевидно, что скорость зависит от процессора, тактовой частоты и т. Д., Но с чем угодно разумно современный, я все еще ожидал бы время меньше секунды. Конечно, если вы решите записать простые числа в файл, вы можете ожидать, что это добавит некоторое время, но даже при этом я бы ожидал, что общее время меньше секунды — с относительно медленным жестким диском моего ноутбука, записывающим числа получают всего около 0,6 секунд.

2