Dzień dobry.
Napisałem swego czasu algorytm, który generuje, moim zdaniem, dość szybko liczby pierwsze. Dla przykładu, na i5-6300U @ 2.5 GHz, pierwsze 100 000 liczb pierwszych wygenerował w 0.343 sek, czyli 343 ms. Czy to szybko?
Napiszcie, proszę, jak to wygląda u Was. Mój algorytm jest sprytny. Ale pewne już ktoś go wymyślił.
Dzięki
Michał
To nic; właśnie sprawdziłem swój algorytm i wygenerował tyle samo liczb w 21.37ms.
Napisałem naiwny generator, 100k w 55ms, 500k w 530ms (Intel(R) Core(TM) i5-6402P CPU @ 2.80GHz).
Na wandboksie ciut wolniej.
https://wandbox.org/permlink/adDQORhdM3l4Gyfk
Jak napiszę generator w całości w czasie kompilacji w szablonach C++ to się nie pozbierasz z tymi trzystoma milisekundami.
Mój algorytm wykorzystuje obserwację, że liczba pierwsza to taka, która nie dzieli się przez inną l. pierwszą. I to cały sekret.
Udoskonaliłem go o te += 6 (+-1)
#include <iostream>
#include <cmath>
#include <ctime>
#define ROZMIAR 100000
bool czyPierwsza(unsigned int i, unsigned int * tab, unsigned int n)
{
double maxi = std::sqrt(i);
for (unsigned int j = 0; tab[j] <= maxi && j < n; j++)
if (i % (*(tab + j)) == 0)
return false;
return true;
}
int main()
{
using namespace std;
unsigned long long start = clock();
unsigned int tab[ROZMIAR] = {2, 3};
unsigned int j = 2;
for (unsigned int i = 6; j < ROZMIAR; i += 6)
{
if (czyPierwsza(i - 1, tab, ROZMIAR))
(*(tab + j++)) = i - 1;
if (czyPierwsza(i + 1, tab, ROZMIAR))
(*(tab + j++)) = i + 1;
}
for (int i = 0; i < ROZMIAR; i++)
cout << (*(tab + i)) << " ";
cout << endl << "!" << ((clock() - (double)start) / CLOCKS_PER_SEC) << "!";
return 0;
}
Wersja poprawiona wskazówką kq.
#include <iostream>
#include <cmath>
#include <ctime>
#define ROZMIAR 100000
bool czyPierwsza(unsigned int i, unsigned int * tab, unsigned int n)
{
int maxi = std::sqrt(i);
for (unsigned int j = 0; tab[j] <= maxi && j < n; j++)
if (i % (*(tab + j)) == 0)
return false;
return true;
}
int main()
{
using namespace std;
unsigned long long start = clock();
unsigned int tab[ROZMIAR] = {2, 3};
unsigned int j = 2;
for (unsigned int i = 6; j < ROZMIAR; i += 6)
{
if (czyPierwsza(i - 1, tab, ROZMIAR))
(*(tab + j++)) = i - 1;
if (czyPierwsza(i + 1, tab, ROZMIAR))
(*(tab + j++)) = i + 1;
}
for (int i = 0; i < ROZMIAR; i++)
cout << (*(tab + i)) << " ";
cout << endl << "!" << ((clock() - (double)start) / CLOCKS_PER_SEC) << "!";
return 0;
}
mpaw napisał(a):
(*(tab + j++)) = i + 1;
Takie pseudohackerstwo jest bez sensu. Jaśnie, i mniejszą ilością literek jest
tab[j++] = i+1;
Spróbujcie jeszcze dodać przetwarzanie równoległe.
Skompilujcie na komputerze kwantowym, patentujcie, publikujcie w topowych periodykach :-p Będzie czad po odpaleniu benchmarków!
MSPANC
robotę można podzielić, najpierw znaleźć pierwsze mniejsze od maxi a potem niech GPU równolegle męczy, ale to nie mój pomysł , z książki wzięty
@mpaw: to teraz porównaj wydajność swojego programu z tym http://cr.yp.to/primegen.html :)