Sortie des nombres premiers à proximité

9

Écrivez un programme qui prend une entrée (qui peut ou non être un nombre premier) et répertorie le nombre premier immédiat qui le suit et le précède.

Exemple d'entrée:

1259

Exemple de sortie:

1249 1277

Le programme le plus court gagne. Doit s'exécuter dans les 10 secondes sur un PC de bureau moderne. Les entrées seront limitées à 10 000 maximum.

code-golf number primes Thomas O
la source
2
Il semble quelque peu étrange d'énumérer une limite de temps sans limiter également la plage des entrées possibles. Sommes-nous obligés de trouver des nombres premiers de plusieurs milliers de chiffres en dix secondes?
Anon.
@Anon. Supposons que je ne donne pas d'entrées ridicules, mais le programme doit être quelque peu optimisé. J'ai clarifié le texte de la question.
Thomas O
mon one-liner est tout sauf optimal, mais il fonctionne en ~ 1s pour une entrée de 10000. Vous devez vraiment essayer d'avoir besoin de 10s.
ninjalj
@ninjalj Juste pour éliminer des algorithmes absolument horribles.
Thomas O
3
donc vous ne pensez pas à tester un nombre npour la primauté en créant une chaîne de ncaractères longue et en testant cela contre une expression régulière absolument horrible?
ninjalj

Réponses:

6

Perl 5.10 (perl -E), 65 caractères

La moitié du crédit (au moins) devrait aller à @J B.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
ninjalj
la source
agréable! le premier test regex!
Ming-Tang
oui, je l'ai appris sur stackoverflow.com/questions/3543811/code-golf-happy-primes
ninjalj
On dirait que vous pourriez enregistrer quelques caractères avec une expression régulière citée (+2 pour le qr, -4 pour ne pas avoir besoin des délimiteurs plus tard).
Anon.
En fait, cela fonctionne sans qr. LMGTFY: 81 caractères$m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"
JB
Deuxième tour, en tenant compte des deux matchs de motif (66 caractères):perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}'
JB
12

Mathematica , 19

#~NextPrime~{-1,1}&
Mr.Wizard
la source
très intelligent: 0)
Dr belisarius
10

Mathematica: 28 caractères

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

Usage

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
Dr. belisarius
la source
3

Python - 93

Basé sur la réponse de fR0DDY . J'ai essentiellement fusionné les lignes 4 et 5 et raccourci la ligne 2 en utilisant une méthode différente.

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
la source
2

Python 116 111 109 Caractères 

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
la source
1
utilisationf=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))
st0le
@ fR0DDY, au lieu d'utiliser les 3 premières lignes n=input()-1et m=n+2, enregistre 3 caractères ... je pense.
st0le
et peut-être vous pouvez remplacer not(all(...))en any(...)inversant les booléens
st0le
Vous ne comptez pas de nouvelles lignes. Le nombre réel est 108.
JPvdMerwe
1
Veuillez également compter les nouvelles lignes dans le nombre de vos personnages. -1 pour avoir trompé les autres.
moinudin
2

J, 22 caractères

(_4&p:,4&p:)(".stdin)_
Gareth
la source
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..]

Exemple

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

Python, 116 139 caractères (le double retrait est tab-char)

Utilise un bon tamis d'ératosthène

Modifications et (merci à TON @JPvdMerwe). Devrait fonctionner avec des nombres premiers maintenant.

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.
la source
-1 Pour ne pas compter les espaces blancs NÉCESSAIRES .
JPvdMerwe
@JPvdMerwe Ma faute, je suis nouveau ici, et j'ai réalisé que j'ai peut-être utilisé la mauvaise métrique de mon éditeur.
Doug T.
@JPvDMerwe remercie également pour l'aide sur les modifications
Doug T.
@DougT cool tout le monde fait une erreur :) +1 Pour inverser mon vote négatif, assurez-vous simplement la prochaine fois.
JPvdMerwe
Une astuce que vous pouvez faire est de déplacer les lignes 1 à 3 sous la ligne 4 et de les remplacer a=range(9999)par a=range(n). Toujours dans la ligne 2, vous n'avez pas besoin de passer aau lambda, vous pouvez simplement l'utiliser. Cela devrait raser beaucoup.
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,_))

non golfé:

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 secondes pour exécuter tous les 9998 pouces de 3 à 10 000

Utilisateur inconnu
la source
1

Swift 190 187 185 110

Swift est très mauvais en code-golf, mais je l'ai quand même essayé: D
Il devient de plus en plus court ... (Merci à @HermanLauenstein d' avoir supprimé 75 octets)

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
la source
-75 octets avec beaucoup de restructuration 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)}(je ne l'ai pas encore testé correctement)
Herman L
Merci @HermanLauenstein. C'est mon premier code-golf, donc j'ai besoin de toute aide :)
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)

NOTE: Le Primesmodule a été écrit par moi mais il existait avant que cette question ne soit posée. Il n'a PAS été écrit pour cela. Néanmoins, cela a été jugé injuste, voici donc la version mise à jour.

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
la source
Je ne sais pas comment vous avez réussi à vous tromper mais c'est en fait:123
JPvdMerwe
Aussi, @John, sauf si le module fait maintenant partie du langage, dans un souci d'équité, vous devez inclure le code. Mais bravo pour l'honnêteté.
JPvdMerwe
Je pense que c'est tricher à utiliser Primes; contre l'esprit du golf de code.
Thomas O
@JPv: Hein. Il était faux. Je me demande comment cela s'est produit.
John
@Thomas, @JPv: J'ai publié une version mise à jour sans l'importation.
John
0

C (gcc) , 98 octets

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);}

Essayez-le en ligne!

Version complète du programme, C (gcc) , 116 octets

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);}

Essayez-le en ligne!

Les deux versions supposent que nous ne testons jamais 1 pour la primauté, ce qui ne se produit que si l'entrée est inférieure ou égale à 2, auquel cas la sortie ne serait de toute façon pas définie.

gastropner
la source