Bibliotekarz przyłapał cię na oszukiwaniu w pracy za pomocą algorytmu sortowania , więc teraz jesteś karany. Nakazano ci utworzyć kod, aby bibliotekarz mógł wywrzeć wrażenie na obiekcie, którego nie odczuwał, uczuciu matematyki. Więc to , co „inne obowiązki przypisane” środków ...

Wszyscy znają naturalną sekwencję liczb w bazie 10, zwaną N :

0, 1, 2, 3, 4, 5, 6, ...

Na tej podstawie możemy wygenerować sekwencję liczb pierwszych, nazwijmy ją P , tak że każdy element w P ma dokładnie dwa dzielniki w N , a mianowicie 1sam. Ta sekwencja to:

2, 3, 5, 7, 11, 13, ...

OK, jak na razie dość rutyny.

Bibliotekarz pomyślał o fajnej funkcji F (x, y), która pobiera liczbę xz N , z warunkiem 0 <= x <= 9i liczbę yz N , i wstawia xdo yrozwinięcia dziesiętnego w każdej pozycji (tj. Wstawianie, wstawianie lub dołączanie xdo y), a następnie zwraca posortowany zestaw nowych liczb.
Na przykład F (6, 127) spowoduje

1267, 1276, 1627, 6127

Ale to wciąż trochę nudne. Bibliotekarz chce urozmaicić sprawę nieco bardziej , określając nową funkcję z -> {p : p in P and F(z,p) subset of P}, posortowaną rosnąco.
Na przykład, z (7) byłoby

3, 19, 97, 433, 487, 541, ...

ponieważ 37i 73są zarówno pierwsi, jak 719 179i 197wszyscy pierwsi, itp.

Zauważ, że z (2) jest puste, ponieważ żadna liczba pierwsza z 2dołączonym nigdy nie będzie pierwsza Podobnie dla {0,4,5,6,8}.

Twoim zadaniem jest napisanie kodu, który wygeneruje i wyśle ​​pierwsze 100 liczb w sekwencji z (x) dla danego x .

Wejście

Pojedyncza liczba całkowita x taka, że 0 <= x <= 9. Dane wejściowe można wprowadzać za pomocą argumentu funkcji, STDIN lub równoważnego.

Wynik

Sekwencja pierwszych 100 liczb, ograniczona przez wybór, do STDOUT lub równoważnej, tak że sekwencja spełnia z (x) jak opisano powyżej. Jeśli z (x) jest puste, tak jak w przypadku {0,2,4,5,6,8}, Empty Setzamiast tego należy podać słowa .

Ograniczenia

• To jest kod-golf, ponieważ musisz zapisać to na kartę indeksową, aby bibliotekarz mógł pokazać nauczyciela matematyki, a twoja ręka łatwo się kurczy.
• Obowiązują standardowe ograniczenia luk. Bibliotekarz nie toleruje oszustów.

Sekwencje referencyjne

x = 1: A069246
x = 3: A215419
x = 7: A215420
x = 9: A215421

Powiązane: Znajdź największą kruchą liczbę pierwszą / Znajdź najmniejszą liczbę pierwszą z podłańcucha / Znajdź największą liczbę pierwszą, która wciąż jest liczbą pierwszą po usunięciu cyfry

Pyth, 49 bajtów

Podobnie jak Python3 i inne odpowiedzi w języku Pyth, środowisko wykonawcze do znalezienia 100 liczb jest zabronione. (pakiet testowy daje 10)

?}z"1379".f&!tPZ!|FmtPvjzc`Z]dhl`Z*TT3"Empty Set"

Wypróbuj online

Python 3, 188 bajtów

x=input()
k=1
i=100
if x in"024568":i=print("Empty Set")
while i:k+=1;s=str(k);i-=all(sum(p%d<1for d in range(2,p))<4for p in[k*int(s[:j]+x+s[j:])for j in range(len(s)+1)])and not print(k)

Źle grał w golfa, ale na razie jest coś. Zamiast sprawdzania sprawdzamy p in P and F(z,p) subset of P, że p*fjest to semiprime dla każdego f in F(z,p). Połącz to z podziałem prób na testy pierwotności, a otrzymasz O(scary)algorytm.

Perl, 124 bajty

$p=prime_iterator;y/1379//or$i=+~print'Empty Set'}while($i<100){$_=&$p;is_prime"$`@F$'"or redo while//g;$i++

Wymaga następującej opcji wiersza poleceń:, -palMntheory=:allliczone jako 16. Dane wejściowe pobrane ze standardowego wejścia.

Zastosowania @DanaJ „s Math::Prime::Utilmoduł Perl (ładowany pragmie ntheory). Zdobądź dzięki:

cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

is_primejest deterministyczny dla wszystkich wartości mniejszych niż 2 ⁶⁴ , co jest wystarczające dla naszych celów.

Przykładowe użycie

$ echo 2|perl -palMntheory=:all oscary.pl
Empty Set

$ echo 7|perl -palMntheory=:all oscary.pl
3
19
97
433
487
541
691
757
853
1471
.
.
.
718705783
720574573
737773357
745157779
747215167
767717017
768743377
770294977
771778477
774577777

Oczekiwane czasy działania

x = 1 : 1 m 09,2 s
x = 3 : 0 m 04,2 s
x = 7 : 2 m 52,5 s
x = 9 : 0 m 11,5 s

Pyth, 58

L}bPb|*"Empty Set"}Qj204568T.f&yZ.Amyi++<JjZTdQ>JdThl`Z100

Ten zestaw testów oblicza tylko pierwsze 10 liczb, ponieważ wygenerowanie reszty zajmuje dużo czasu. Brute wymusza zarówno pierwotność, jak i wstawianie cyfr. Demonstruje tak niską wydajność, że nie byłem w stanie uruchomić jej do 100, więc proszę powiedz mi, jeśli są jakieś problemy.