Primzahlen in der Nähe ausgeben

9

Schreiben Sie ein Programm, das eine Eingabe (die eine Primzahl sein kann oder nicht) nimmt und die unmittelbare Primzahl auflistet, die darauf folgt und davor steht.

Beispieleingabe:

1259

Beispielausgabe:

1249 1277

Das kürzeste Programm gewinnt. Muss auf einem modernen Desktop-PC innerhalb von 10 Sekunden ausgeführt werden. Die Eingänge sind auf maximal 10.000 begrenzt.

code-golf number primes Thomas O.
quelle
2
Es erscheint etwas seltsam, ein Zeitlimit aufzulisten, ohne auch den Bereich möglicher Eingaben einzuschränken. Müssen wir innerhalb von zehn Sekunden mehrere tausendstellige Primzahlen finden?
Anon.
@ Anon. Angenommen, ich werde keine lächerlichen Eingaben machen, aber das Programm muss etwas optimiert werden. Ich habe den Fragentext geklärt.
Thomas O
Mein Einzeiler ist alles andere als optimal, aber er läuft in ~ 1s für eine Eingabe von 10000. Sie müssen sich wirklich anstrengen, um 10s zu benötigen.
Ninjalj
@ninjalj Nur um absolut schreckliche Algorithmen auszusortieren.
Thomas O
3
Sie ziehen es also nicht in Betracht, eine Zahl nauf Primalität zu ntesten, indem Sie eine lange Zeichenfolge erstellen und diese gegen einen Regex testen, der absolut schrecklich ist?
Ninjalj

Antworten:

6

Perl 5,10 (Perl-E), 65 Zeichen

Die Hälfte des Guthabens sollte (mindestens) an @J B gehen.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
Ninjalj
quelle
nett! der Prime Test Regex!
Ming-Tang
Ja, ich habe es unter stackoverflow.com/questions/3543811/code-golf-happy-primes
ninjalj
Scheint, als könnten Sie ein paar Zeichen mit einem Anführungszeichen in Anführungszeichen speichern (+2 für die qr, -4, wenn Sie die Trennzeichen später nicht benötigen).
Anon.
Eigentlich funktioniert es ohne qr. LMGTFY: 81 Zeichen$m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"
JB
Zweite Runde unter Berücksichtigung beider Musterübereinstimmungen (66 Zeichen):perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}'
JB
11

Mathematica , 19

#~NextPrime~{-1,1}&
Mr.Wizard
quelle
sehr klug: 0)
Dr. belisarius
10

Mathematica: 28 Zeichen

(k=NextPrime;{k[#,-1],k@#})&

Verwendungszweck

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
Dr. Belisarius
quelle
3

Python - 93

Basierend auf der Antwort von fR0DDY . Grundsätzlich habe ich die Zeilen 4 und 5 zusammengeführt und die Zeile 2 mit einer anderen Methode gekürzt.

n=input()-1
m=n+2
f=lambda n:any(n%x<1for x in range(2,n))
exec"n-=f(n);m+=f(m);"*m
print n,m
JPvdMerwe
quelle
2

Python 116 111 109 Zeichen 

n=input()-1
m=n+2
f=lambda n:any(pow(b,n-1,n)>1for b in(3,5,7,13))
while f(n):n-=1
while f(m):m+=1
print n,m
fR0DDY
quelle
1
usef=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))
st0le
@ fR0DDY, anstelle der ersten 3 Zeilen verwenden n=input()-1und m=n+2, spart 3 Zeichen ... denke ich.
st0le
und vielleicht können Sie ersetzen, not(all(...))indem Sie any(...)die Booleschen
Werte
Sie zählen keine neuen Zeilen. Die tatsächliche Anzahl ist 108.
JPvdMerwe
1
Bitte zählen Sie auch die Zeilenumbrüche in Ihrer Charakteranzahl. -1 für die Täuschung anderer.
Moinudin
2

J, 22 Zeichen

(_4&p:,4&p:)(".stdin)_
Gareth
quelle
1

Haskell: 99

s(z:y)=z:s[x|x<-y,mod x z>0];f(x:y:z:w)=(x,z):f(y:z:w);p x=(head.filter(\(c,v)->c<x&&v>x).f.s)[2..]

Beispiel

Main> p 1259
(1249,1277)
Ming-Tang
quelle
1

Python, 116 139 Zeichen (doppelter Einzug ist Tabulatorzeichen)

Verwendet ein gutes altes Sieb von Eratosthenes

Bearbeitungen und (danke an TON @JPvdMerwe). Sollte jetzt mit Primzahlen arbeiten.

l=n=input();a=range(n*2)
for i in a[2:]:a=[k for k in a if k==i or k%i]
for g in a:
 if g>n:print l,g;break
 if i!=n:l=g

Original

a=range(9999)
j=lambda a,n:[i for i in a if i==n or i%n]
for i in a[2:]:a=j(a,i)
o=n=input();
for i in a:
 if o<n and i>n: 
  print o,i
 o=i
Doug T.
quelle
-1 Zum Nichtzählen der erforderlichen Leerzeichen.
JPvdMerwe
@JPvdMerwe Meine Schuld, ich bin neu hier und habe festgestellt, dass ich möglicherweise die falsche Metrik aus meinem Editor verwendet habe.
Doug T.
@ JPVDMerwe auch danke für die Hilfe bei den Änderungen
Doug T.
@DougT cool, jeder macht einen Fehler :) +1 Um meine Abstimmung rückgängig zu machen, stellen Sie beim nächsten Mal sicher, dass
JPvdMerwe
Ein Trick , den Sie tun können , ist Linien zu bewegen 1-3 unterhalb der Linie 4 und ersetzen a=range(9999)mit a=range(n). Auch in Zeile 2 müssen Sie nicht zum aLambda übergehen , Sie können es einfach verwenden. Dies sollte sich viel rasieren.
JPvdMerwe
1

Scala 119:

def p(n:Int)=(2 to n-1).exists(n%_==0)
def i(n:Int,v:Int):Int=if(!p(n+v))n+v else i(n+v,v)
Seq(-1,1).map(i(readInt,_))

ungolfed:

def notPrime (n:Int) = 
    (2 to n-1).exists (n % _ == 0)

def itPrime (n: Int, vector:Int) : Int =
    if (! notPrime (n+vector)) n+vector
    else itPrime (n+vector, vector)

def nearbyPrime (value: Int) =
    Seq (-1, 1).map (sign => itPrime (value, sign))

21,2 Sekunden, um alle 9998 Ints von 3 bis 10.000 auszuführen

Benutzer unbekannt
quelle
1

Swift 190 187 185 110

Swift ist sehr schlecht im Code-Golf, aber ich habe es trotzdem versucht: D
Es wird immer kürzer ... (Danke an @HermanLauenstein für das Entfernen von 75 Bytes)

var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}
Josef Zoller
quelle
-75 Bytes mit viel Restrukturierung var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}(ich habe es noch nicht richtig getestet)
Herman L
Danke @HermanLauenstein. Es ist mein erster Code-Golf, also kann ich jede Hilfe brauchen :)
Josef Zoller
0

Python (123)

import Primes as p
j=i=int(input())
n=p.primes(i*2)
while not i in n[:]:
 i+=1
print(i)
while not j in n[:]:
 j-=1
print(j)

HINWEIS: Das PrimesModul wurde von mir geschrieben, war jedoch vorhanden, bevor diese Frage gestellt wurde. Es wurde NICHT dafür geschrieben. Trotzdem wurde dies als unfair angesehen, daher hier die aktualisierte Version.

Python (215)

j=i=int(input())
import math as m
s=list(range(i*2))
for n in s[:]:
 for l in range(1,int(m.ceil(m.sqrt(n)))):
  if(n%l)==0and l!=1and n in s:s.remove(n)
while not i in s:i+=1
print(i)
while not j in s:j-=1
print(j)
John
quelle
Ich weiß nicht, wie Sie es geschafft haben, Ihre Zählung falsch zu machen, aber es ist tatsächlich:123
JPvdMerwe
@John, es sei denn, das Modul ist jetzt Teil der Sprache, sollten Sie im Interesse der Fairness den Code einfügen. Aber ein großes Lob an die Ehrlichkeit.
JPvdMerwe
Ich denke, es ist Betrug zu benutzen Primes; gegen den Geist des Code Golf.
Thomas O
@ JPV: Huh. Es war falsch. Ich frage mich, wie das passiert ist.
John
@Thomas, @JPv: Ich habe eine aktualisierte Version ohne Import veröffentlicht.
John
0

C (gcc) , 98 Bytes

p(n,i){for(i=2;i<n;)n=n%i++?n:0;i=n;}g(n,d){for(;!p(n+=d););printf("%d ",n);}f(n){g(n,-1);g(n,1);}

Probieren Sie es online aus!

Vollprogrammversion, C (gcc) , 116 Bytes

p(n,i){for(i=2;i<n;)n=n%i++?n:0;i=n;}g(n,d){for(;!p(n+=d););printf("%d ",n);}main(n){scanf("%d",&n);g(n,-1);g(n,1);}

Probieren Sie es online aus!

Beide Versionen gehen davon aus, dass wir 1 niemals auf Primalität testen. Dies geschieht nur, wenn die Eingabe 2 oder niedriger ist. In diesem Fall wäre die Ausgabe ohnehin undefiniert.

Gastropner
quelle