Saída de números primos próximos

9

Escreva um programa que utilize uma entrada (que pode ou não ser primo) e lista o primo imediato a seguir e precedendo.

Exemplo de entrada:

1259

Exemplo de saída:

1249 1277

O programa mais curto vence. É necessário executar dentro de 10 segundos em um PC de mesa moderno. As entradas serão limitadas a 10.000 no máximo.

code-golf number primes Thomas O
fonte
2
Parece um tanto estranho listar um limite de tempo sem também limitar o intervalo de entradas possíveis. Somos obrigados a encontrar números primos de vários milhares de dígitos em dez segundos?
Anon.
@Anon. Suponha que não darei contribuições ridículas, mas o programa deve ser um pouco otimizado. Esclareci o texto da pergunta.
Thomas O
meu one-liner é tudo menos ideal, mas é executado em ~ 1s para uma entrada de 10000. Você precisa se esforçar muito para precisar de 10s.
Ninjalj
@ ninjalj Apenas para eliminar algoritmos absolutamente terríveis.
Thomas O
3
para que você não considere testar um número nde primalidade criando ncaracteres de seqüência de caracteres longos e testando isso em uma regex absolutamente horrível?
Ninjalj 17/02

Respostas:

6

Perl 5.10 (perl-E), 65 caracteres

Metade do crédito (pelo menos) deve ir para @J B.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
ninjalj
fonte
agradável! o regex de teste principal!
Ming-Tang
sim, eu aprendi sobre ele em stackoverflow.com/questions/3543811/code-golf-happy-primes
ninjalj
Parece que você pode salvar alguns caracteres com uma expressão regular entre aspas (+2 para qr-4, por não precisar dos delimitadores posteriormente).
Anon.
Na verdade, funciona sem qr. LMGTFY: 81 caracteres$m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"
JB
Segunda rodada, fatorando as duas correspondências de padrões (66 caracteres):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
fonte
muito inteligente: 0)
Dr. belisarius
10

Mathematica: 28 caracteres

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

Uso

%[1259]
{1249, 1277}  

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

Python - 93

Com base na resposta de fR0DDY . Basicamente, mesclei as linhas 4 e 5 e reduzi a linha 2 usando um método diferente.

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
fonte
2

Python 116 111 109 Personagens 

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
fonte
11
usef=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))
st0le
@ fR0DDY, em vez de usar as 3 primeiras linhas n=input()-1e m=n+2, salva 3 caracteres ... eu acho.
7111 sthle
e talvez você pode substituir not(all(...))por any(...)invertendo os booleans
st0le
Você não conta novas linhas. A contagem real é 108.
JPvdMerwe
11
Além disso, conte novas linhas na contagem de caracteres. -1 por enganar os outros.
moinudin
2

J, 22 caracteres

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

Exemplo

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

Python, 116 139 caracteres (o recuo duplo é tab-char)

Usa boa peneira antiga de Eratóstenes

Edita e (graças a TON @JPvdMerwe). Deve funcionar com números primos agora.

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.
fonte
-1 Para não contar o espaço em branco NECESSÁRIO .
precisa saber é o seguinte
@JPvdMerwe Minha culpa, sou novo aqui, e percebi que posso ter usado a métrica errada do meu editor.
Doug T.
@JPvDMerwe também obrigado pela ajuda nas edições
Doug T.
@DougT legal, todo mundo comete um erro :) +1 Para reverter meu voto negativo, apenas certifique-se da próxima vez.
JPvdMerwe
Um truque que você pode fazer é mover as linhas 1-3 abaixo da linha 4 e substituí a=range(9999)- las por a=range(n). Também na linha 2 você não precisa passar apara o lambda, basta usá-lo. Isso deve raspar muito.
precisa saber é o seguinte
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,2s para executar todas as 9998 ints de 3 a 10.000

Usuário desconhecido
fonte
1

Swift 190 187 185 110

Swift é muito ruim no código-golfe, mas tentei assim mesmo: D
Está ficando cada vez mais curto ... (Obrigado ao HermanLauenstein por remover 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
fonte
-75 bytes com um monte de reestruturação 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)}(eu não testei ainda corretamente)
Herman L
Obrigado @HermanLauenstein. É o meu primeiro código-golfe, para que eu possa precisar de toda a ajuda :)
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)

NOTA: O Primesmódulo foi escrito por mim, mas existia antes desta pergunta ser feita. NÃO foi escrito para isso. No entanto, isso foi considerado injusto, então aqui está a versão atualizada.

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
fonte
Eu não sei como você conseguiu obter o seu errado contagem, mas na verdade é:123
JPvdMerwe
Além disso, @John, a menos que o módulo faça parte do idioma, no interesse da justiça, você deve incluir o código. Mas parabéns pela honestidade.
JPvdMerwe
Eu acho trapaça usar Primes; contra o espírito do código de golfe.
Thomas O
@JPv: Hein. Ele estava errado. Eu me pergunto como isso aconteceu.
John
@ Thomas, @JPv: Publiquei uma versão atualizada sem a importação.
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);}

Experimente online!

Versão completa do programa, 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);}

Experimente online!

Ambas as versões assumem que nunca testamos 1 quanto à primalidade, o que só acontece se a entrada for 2 ou inferior; nesse caso, a saída seria indefinida de qualquer maneira.

gastropner
fonte