Szybkość generowania liczb pierwszych

0

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ł

0

To nic; właśnie sprawdziłem swój algorytm i wygenerował tyle samo liczb w 21.37ms.

Dowód: https://4programmers.net/Forum/Download/27306

1

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

3

Jak napiszę generator w całości w czasie kompilacji w szablonach C++ to się nie pozbierasz z tymi trzystoma milisekundami.

1

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;
}
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;
}
3
mpaw napisał(a):
  	(*(tab + j++)) = i + 1;

Takie pseudohackerstwo jest bez sensu. Jaśnie, i mniejszą ilością literek jest

tab[j++] = i+1;

0

Spróbujcie jeszcze dodać przetwarzanie równoległe.

1

Skompilujcie na komputerze kwantowym, patentujcie, publikujcie w topowych periodykach :-p Będzie czad po odpaleniu benchmarków!

MSPANC

0

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

1

@mpaw: to teraz porównaj wydajność swojego programu z tym http://cr.yp.to/primegen.html :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1