W 1946 r. Erdos i Copeland udowodnili, że pewna liczba jest liczbą normalną , tzn. Cyfry w liczbach dziesiętnych są równomiernie rozmieszczone.

Użytkownicy wprowadzą sekwencję cyfr, a znajdziesz najmniejszą liczbę pierwszą zawierającą ten ciąg w bazie 10.

Przykład:

input   -> output
"10"    -> 101
"03"    -> 103
"222"   -> 2221
"98765" -> 987659

Najkrótszy kod w bajtach wygrywa. Wiem, że niektóre języki (matematyka, szałwia, pari-gp ...) mają wbudowane funkcje związane z liczbami pierwszymi. -50 bajtów, jeśli twój program nie polega na takich funkcjach. Nie próbuj oszukiwać, proszę, jeśli twój język ma już ogromną przewagę, nie rób bonusu.

Edytować

Według kilku poniższych komentarzy najmniejsza liczba pierwsza zawierająca „03” to 3. Czy to naprawdę robi różnicę? Jedyne, o czym myślę, to to, że może liczby są łatwiejsze w obsłudze niż łańcuchy.

W przypadkach takich jak „03” preferowanym wyjściem byłoby 103. Jednak nie uważam, aby była to podstawowa część twojego programu, więc możesz zignorować wszelkie początkowe zero, jeśli zapewni to mniejszą liczbę bajtów.

Golfscipt, 33 32 bajty = wynik -18

2{:x,2>{x\%!},!!x`3$?)!|}{)}/;;x

Wyjaśnienie:

• 2{...}{)}/- zaczynając od 2, gdy coś jest prawdą, zwiększaj górę stosu

• ;;x- odrzucić wartości pośrednie zebrane przez {}{}/i dane wejściowe, a następnie umieścić tam ostatnią testowaną wartość

• :x,2>- zapisz wartość jako x, a następnie utwórz listę od 2dox-1

• {x\%!},!!- zachowaj te, które xsą podzielne, a następnie przymusz do wartości logicznej (nie pustej)
• x`3?)!- wyszukaj dane wejściowe w formie tekstowej x( -1jeśli nie znaleziono), zwiększaj, neguj.
• | - lub

Program Haskell, 97 znaków = 47 punktów

main=getLine>>= \i->print$head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]

Funkcja Haskell, 75 znaków = 25 punktów

p i=head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]

rodzaj pjest (Integral a, Show a) => [Char] -> a. Jeśli podasz swój własny typ całkowy, możesz wyszukiwać przez infix we własnej reprezentacji tych wartości. Standard Integerużywa oczekiwanej notacji dziesiętnej dla liczb całkowitych.

Niezbyt szybko. Kwadratowa w wartości (nie rozmiarze) wyniku.

wersja bez golfa:

import Data.List
leastPrime infix = head $ filter prime' [2..]
  where prime' x  = all (\n-> x`mod`n /= 0) [2..x-1]
                 && i `isInfixOf` show x
main = print . leastPrime =<< getLine

przykład:

Prelude> let p i=head$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]
Prelude> p "0"
101
Prelude> p "00"
1009
Prelude> p "000" -- long pause
10007

Java - 175 znaków.

class s{public static void main(String[]a){int i,n=2,p;for(;;){p=1;for(i=3;i<n;i++)if(n%i==0)p=0;if((n==2||p>0)&&(""+n).indexOf(a[0])>=0) {System.out.println(n);break;}n++;}}}

Mathematica 58

(n=1;While[StringCases[ToString[p=Prime@n],#]=={},n++];p)&

Względne czasy na moim komputerze Mac (2,7 GHz i7 z pamięcią 8 GB).

Znajdź najmniejszą liczbę pierwszą zawierającą „01”.

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["01"]]

{0,000217, 101}

Znajdź najmniejszą liczbę pierwszą zawierającą „012345”.

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["012345"]]

{5.021915, 10123457}

Znajdź najmniejszą liczbę pierwszą zawierającą „0123456”.

AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["0123456"]]

{87.056245, 201234563}

Sage , 72

Działa w interaktywnym pytaniu

a=raw_input()
i=0
p=2
while a not in str(p):i+=1;p=Primes().unrank(i)
p

Primes().unrank(i)daje iczwartą liczbę pierwszą, przy czym 0 jest liczbą 2.

R, 56 znaków -50 = 6

k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k

Weź dane jako standardowe. Przyrosty k, aż k jest liczbą pierwszą (testowane przez zsumowanie instancji, dla których k mod 2 do k są zerami, stąd FAŁSZ, ponieważ 0 zamienione w logiczną jest FAŁSZ) i zawiera ciąg podany jako dane wejściowe (testowany prostym grepem, tutaj grepl ponieważ chcemy logicznego wyniku).

Stosowanie:

> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "03"
2: 
Read 1 item
[1] 103
> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "003"
2: 
Read 1 item
[1] 2003

Shell Oneliner (Coreutils): 45 znaków

Nie definiujemy tutaj funkcji ... tylko oneliner, który przyjmuje jeden argument $ni skanuje zakres liczb całkowitych (właściwie trochę więcej, aby skrócić kod). Wersja 55 znaków:

seq 5e9|grep $n|factor|awk '{if(NF==2)print $2}'|head -n1

Nie jest nawet zbyt wolny. Na n=0123456to zwraca 201234563się 81.715s. To imponująco szybkie jak na długi potok z dwoma procesorami łańcuchowymi.

Usuwając dwie postacie (do 53) i jedną fajkę, możemy uruchomić ją jeszcze szybciej:

seq 5e9|grep $n|factor|awk '{if(NF==2){print $2;exit}}'

I wreszcie, trochę sedmagii, aby sprowadzić go do 45 znaków , chociaż wydruk jest brzydki:

seq 5e9|grep $n|factor|sed -n '/: \w*$/{p;q}'

n = 000 -> 10007: 10007 (użytkownik 0,017 s)

n = 012345 -> 10123457: 10123457 (użytkownik 7.11s)

n = 0123456 -> 201234563: 201234563 (użytkownik 66,8 s)

J - 38 znaków -50 = -12 pkt

Zwykle w J używałbyś bardzo zoptymalizowanych wbudowanych funkcji liczb pierwszych, więc nie będę przepraszać za powolność działania.

>:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2

Wyjaśniono:

• >:@]^:(...)^:_&2- Począwszy od 2, zwiększaj, aż (...)zwraca false.
• (+.i.)@]- Weź GCD licznika z każdą liczbą całkowitą mniejszą od niego. (Stosujemy konwencję GCD (X, 0) = X.)
• ]=*/@- Weź iloczyn wszystkich tych liczb i sprawdź równość licznika. Jeśli licznik jest liczbą pierwszą, lista zawierała wszystkie 1 s, z wyjątkiem GCD z 0; w przeciwnym razie będzie co najmniej jeden GCD, który jest większy niż 1, więc produkt będzie większy niż licznik.
• >./@(E.":)- Sprawdź, czy reprezentacja ciągu licznika ( ":) zawiera ciąg ( E.) w dowolnym punkcie. >./jest funkcją maksimum i używamy jej, ponieważ E.zwraca wektor boolowski z wartością 1 wszędzie tam, gdzie podłańcuch zaczyna się w głównym ciągu.
• *:- Logiczne NAND wyniki razem. Będzie to fałsz tylko wtedy, gdy oba dane wejściowe były prawdziwe, tj. Jeśli licznik był pierwszy i zawierał podłańcuch.

Stosowanie:

   >:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '03'
103
   >:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '713'
2713

Dla potomnych, oto wersja z wbudowanym prime (30 znaków, ale bez premii):

>:@]^:(>./@(E.":)*:1 p:])^:_&2

1 p:] sprawdza licznik pod kątem pierwszeństwa zamiast sztuczki GCD.

Brachylog (v2), 3 bajty w kodowaniu Brachylog

ṗ≜s

Wypróbuj online!

Podanie funkcji, przyjmowanie danych wejściowych z argumentu po prawej stronie, dawanie wyniku przez mutowanie argumentu po lewej stronie. (Jest to przeciwieństwo normalnej konwencji Brachylog; zobacz ten meta post, aby uzyskać więcej dyskusji. Zamiana argumentów na bardziej typową kolejność kosztowałaby trzy bajty.) Łącze TIO ma opakowanie, które wywołuje funkcję z odpowiednią konwencją wywoływania i drukuje wynik.

Wyjaśnienie

ṗ≜s
 ≜   Find the integer closest to zero
ṗ      which is prime {implicit: and output it via the left argument}
  s    and which is a substring of the {right argument}

Niestety Brachylog jest tak odpowiedni dla tego problemu, że zgodnie z zasadami problemu nie mogę nawet próbować skorzystać z premii (co jak na ironię oznacza, że ​​nie jest w stanie wygrać).

Jednym z powodów, dla których tak bardzo lubię Brachylog, jest to, że programowanie to komunikacja między człowiekiem a komputerem, a zatem „idealny” język pozwala po prostu bezpośrednio przetłumaczyć specyfikację problemu na angielski; pomysły, za pomocą których stwierdzono problem i za pomocą których napisany jest program, byłyby takie same. Brachylog może zaskakiwać często tym ideałem; pytanie tutaj brzmi: „znajdź najmniejszą liczbę pierwszą zawierającą podłańcuch”, i mogę dosłownie połączyć ze sobą pojęcia „najmniejsza liczba pierwsza, zawierająca podłańcuch” we właściwej kolejności i mieć działający program. W związku z tym Brachylog mówi o wiele więcej o naturze komunikacji niż język, w którym musiałbyś wyraźnie określić algorytm rozwiązania problemu; czasami rozmawiając z innymi ludźmi, próbujemy wyjaśnić problem, wyjaśniając kroki, które należy podjąć, aby go rozwiązać, ale jest to rzadkie. Dlaczego więc nasze języki powinny być inne?

JavaScript 83 bajty = 33 wynik

Gra w golfa:

for(s=prompt(n=x=0);!n;x++)for(n=(''+x).match(s)?2:0;n&&n<x;n=x%n?n+1:0);alert(x-1)

Niegolfowany (trochę):

s=prompt() // get the input
n = 0
for(x=0;!n;x++) // stop when n is non-zero
    if ((''+x).match(s)) { // if x matches the pattern, check if x is prime
        for(n=2;n&&n<x;)
            n = (x%n == 0) ? 0 : n+1; // if x%n is zero, x is not prime so set n=0
        // if n is non-zero here, x is prime and matches the pattern
    }
alert(x-1)

JavaScript (Node.JS) - 93 bajty = 43 punkty

l:for(i=x=process.argv[2];j=i;i++){while(--j>2)if(!(i%j*(""+i).match(x)))continue l
throw i}

W formie wyodrębnionej z rozsądnymi nazwami zmiennych:

outerLoop:for (currentTry=inputNumber=process.argv[2]; primeIterator=currentTry; currentTry++ ) {
    while (--primeIterator > 2) 
        if(!(currentTry % primeIterator * (""+currentTry).match(inputNumber)))
            continue outerLoop;
    throw i
}

Rdza 0,9 136 bajtów = 86 punktów

fn main(){
   let mut n:u32=2;
   while n.to_str().find_str(std::os::args()[1])==None ||
         range(2,n).find(|&x|n%x==0)!=None {
      n=n+1;
   }
   print!("{}",n);
}

Bardzo wyraźne pomimo zwartości. Za dużo miejsca spędzonego na znalezieniu łańcucha. :(

Tutaj wersja bez białych znaków (136 znaków)

fn main(){let mut n:u32=2;while n.to_str().find_str(std::os::args()[1])==None||range(2,n).find(|&x|n%x==0)!=None{n=n+1;}print!("{}",n);}

Japt, 10 bajtów

_j *ZsøU}a

Spróbuj

Tidy , 37 bajtów

{s:s&{s,p:s in"".p}from primes|first}

Wypróbuj online!

Perl 6 , 36-50 = -14 punktów

{$^a;first {/$a/&&$_%%one ^$_},2..*}

Wypróbuj online!

Biorąc pod uwagę, $_%%one ^$_że jedyne 2 bajty są mniejsze niż .is-prime, myślę, że warto dla bonusu. Upłynął limit czasu dla ostatniego przypadku testowego.

Wyjaśnienie:

{                                  }  # Anonymous code block
 $^a;                                 # Assign input to $a
     first                    ,2..*   # Find the first number
           {                 }        # Which
            /$a/                        # Contains the input
                &&                      # And
                  $_%%one ^$_           # Is prime

Python 3 , 80 79 bajtów - 50 = 30 29 punktów

-1 bajt dzięki kreatywnemu użyciu @ ASCII-only %szamiaststr

Przypadek testowy „98765” nie został jeszcze potwierdzony ze względu na to, jak długo trwa test Potwierdzony dla przypadku testowego „98765” po kilku godzinach, ale z podobnym podejściem, które wykorzystuje ocenę zwarcia, aby uniknąć niektórych testów pierwotności, działa o wiele szybciej. Alternatywnie może to być ~ 2x tak szybko, jeśli wiemy, że „2” nie jest wejściem (możemy uniknąć sprawdzania liczb parzystych pod kątem pierwszeństwa) poprzez ustawienie i=3początkowe i i+=2w pętli, bez dodatkowych kosztów bajtowych.

def f(x):
 i=2
 while(x in"%s"%i)*all(i%j for j in range(2,i))-1:i+=1
 return i

Wypróbuj online!

Objaśnienie whilewarunku ( (x in"%s"%i)*all(i%j for j in range(2,i))-1):

(x in"%s"%i): True/ 1jeśli bieżący licznik zawiera żądaną sekwencję liczb; False/ 0inaczej.

all(i%j for j in range(2,i)): True/ 1jeśli bieżący licznik zawsze ma resztę, gdy jest dzielony przez dowolną liczbę całkowitą od 2 (włącznie) do siebie (wyłączny), tj. jest liczbą pierwszą; False/ 0inaczej.

W *mnoży dwa warunki i działa jako andoperatora - produkt True/ 1wtedy i tylko wtedy, gdy oba te warunki są True/ 1.

-1Działa jako notoperator: False/ 0- 1 wyników w -1, który jest uważany za prawdziwe, natomiast True/ 1- 1 powoduje 0, który jest uważany za fałszywy. Zatem pętla jest kontynuowana, podczas gdy liczba albo nie zawiera żądanej sekwencji liczb, albo nie jest liczbą pierwszą.

Wymień *się andi dodać nawiasy wokół wszystkiego, ale -1za to znacznie szybciej, równoważne rozwiązanie (czyli nieco dłużej).

Rozwiązanie 76 bajtów - 50 = 26 punktów w Pythonie 2 podane tylko przez @ ASCII (wykorzystuje ``zamiast str(),

def f(x):
 i=2
 while(x in`i`)*all(i%j for j in range(2,i))-1:i+=1
 return i

Wypróbuj online!

JavaScript, 65-50 = 15 punktów

x=>(f=y=>(''+y).match(x)&&(p=n=>--n<2||y%n&&p(n))(y)?y:f(y+1))(x)

Wypróbuj online!