Mocno zainspirowany Programowaniem nieskazitelnego świata . Również ściśle związany z tym wyzwaniem .
Zdefiniujmy nieskazitelną liczbę pierwszą jako liczbę, która sama jest liczbą pierwszą, ale nie będzie już liczbą pierwszą, jeśli usuniesz ciągłe podciągi N cyfr 10, gdzie 0 < N < digits in number
.
Na przykład 409 jest nieskazitelną liczbą pierwszą, ponieważ sama 409 jest liczbą pierwszą, ale wszystkie liczby wynikające z usunięcia podłańcucha 1 cyfry nie są liczbą pierwszą:
40
49
09 = 9
a wszystkie liczby wynikające z usunięcia podciągów o długości 2 nie są liczbą pierwszą:
4
9
Z drugiej strony liczba pierwsza 439 nie jest nieskazitelna. Usunięcie różnych podciągów powoduje:
43
49
39
4
9
Podczas gdy 49, 39, 4 i 9 są niepierwotne, 43 jest liczbą pierwszą; dlatego 439 nie jest nieskazitelny.
2, 3, 5 i 7 są nieskazitelnie czyste, ponieważ nie można usunąć żadnych podciągów.
Wyzwanie
Wyzwanie polega na utworzeniu programu lub funkcji, która przyjmuje dodatnią liczbę całkowitą N i wysyła N-tą nieskazitelną liczbę pierwszą. Kod powinien zakończyć się w niecałą minutę na każdym nowoczesnym komputerze PC dla dowolnego wejścia do 50.
Najkrótszy kod w bajtach wygrywa.
Jako odniesienie, oto pierwsze 20 dziewiczych liczb pierwszych:
N Pristine prime
1 2
2 3
3 5
4 7
5 11
6 19
7 41
8 61
9 89
10 409
11 449
12 499
13 821
14 881
15 991
16 6299
17 6469
18 6869
19 6899
20 6949
Oto pełna lista nieskazitelnych liczb pierwszych do 1e7 lub N = 376.
Wreszcie, oto dwa powiązane wpisy OEIS:
źródło