By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
we can see that the 6th prime is 13. What is the 10 001st prime number?
Kod: repozytorium git.
Algorytm
Problem w podejściu naiwnym jest stosunkowo prosty. Generowanie liczb pierwszych wstępnie analizowaliśmy podczas podejścia do problemu #3.
C (variant 1)
W rozwiązaniu tego problemu użyjemy ponownie sprawdzenia czy liczba jest liczbą pierwszą poprzez iterację do wysokości jej pierwiastka. W głównej pętli będziemy wyznaczać i zliczać kolejne liczby pierwsze. Program wypisze zadaną "n-tą" liczbę pierwszą.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <math.h>
/*
* Ideas:
* a) Fermat's Little Theorem, gives looong numbers.
* b) naive: go up to sqrt(n) and just try
* c) AKS test
* d) simple static table of multiples
*
* This implementation does b)rute force.
*/
int is_prime(unsigned long n)
{
unsigned long i;
unsigned long pivot = ceil(sqrt(n));
for(i = 2; i <= pivot; i++) {
if(n % i == 0) {
return 0;
}
}
return 1;
}
int main(int argc, char** argv)
{
char *ptr;
unsigned long nth = (argc > 1 ? strtoul(argv[1], &ptr, 10) : 10001);
if(errno) {
fprintf(stderr, strerror(errno));
return 1;
}
unsigned long counter = 0;
unsigned long n;
for(n = 2; n < ULONG_MAX; n++) {
if(is_prime(n)) {
counter++;
if(counter == nth) {
break;
}
}
}
printf("%ld\n", n);
return 0;
}
Sprawdzamy:
$ for x in 10001 20001 30001 40001 50001 60001 70001 80001 90001; do \
echo "Test: $x"; ./prog.bin $x; \
done
Test: 10001
104743
Test: 20001
224743
Test: 30001
350381
Test: 40001
479939
Test: 50001
611957
Test: 60001
746777
Test: 70001
882389
Test: 80001
1020389
Test: 90001
1159531
Sprawdźmy czas wykonania:
$ for x in 10001 20001 30001 40001 50001 60001 70001 80001 90001; do \
echo "Test: $x"; \
{ time ./prog.bin $x > /dev/null; } 2>&1 | grep real; \
done
Test: 10001
real 0m0.030s
Test: 20001
real 0m0.082s
Test: 30001
real 0m0.150s
Test: 40001
real 0m0.230s
Test: 50001
real 0m0.325s
Test: 60001
real 0m0.438s
Test: 70001
real 0m0.543s
Test: 80001
real 0m0.668s
Test: 90001
real 0m0.796s
A co z dalszymi liczbami pierwszymi?
$ for x in 100001 500001; do \
echo "Test: $x"; \
{ time ./prog.bin $x > /dev/null; } 2>&1 | grep real; \
done
Test: 100001
real 0m0.928s
Test: 500001
real 0m10.789s
Tutaj widzimy przeskok o prawie 10 sekund.
Gdybyśmy znali zakres w jakim n-tej liczby pierwszej szukać, moglibyśmy podejść do problemu o strony generowania liczb pierwszych (choćby sito).
Inne możliwości
Warto tutaj wspomnieć o tej wartościowej odpowiedzi na stackoverflow. Istnieją algorytmy, które są w stanie przybliżyć przedział, w którym możemy szukać n-tej liczby pierwszej.
Przykładem jest właśnie wspomniany na stackoverflow algorytm Meissel-Lehmer.
Implementacje tego algorytmu znajdziemy m.in. na:
Sprawa wygląda obiecująco, zatem postaramy się w przyszłości wrócić do tematu i podjąć próbę stworzenia rozwiązania optymalnego.