Keluarkan bilangan prima terdekat

9

Tulis sebuah program yang mengambil input (yang mungkin atau mungkin bukan prime), dan buat daftar prime langsung berikut dan sebelum itu.

Input contoh:

1259

Contoh output:

1249 1277

Kemenangan program terpendek. Harus dijalankan dalam 10 detik pada PC desktop modern. Input akan dibatasi hingga maksimum 10.000.

code-golf number primes Thomas O
sumber
2
Tampaknya agak aneh untuk menuliskan batas waktu tanpa juga membatasi rentang input yang mungkin. Apakah kita diharuskan menemukan bilangan prima beberapa ribu digit dalam sepuluh detik?
Anon.
@Segera. Asumsikan saya tidak akan memberikan input yang konyol, tetapi programnya harus agak dioptimalkan. Saya telah mengklarifikasi teks pertanyaan.
Thomas O
one-liner saya tidak optimal, tetapi berjalan dalam ~ 1s untuk input 10000. Anda harus berusaha sangat keras untuk membutuhkan 10s.
ninjalj
@ninjalj Hanya untuk menyingkirkan algoritma yang benar-benar mengerikan.
Thomas O
3
jadi kamu tidak mempertimbangkan menguji angka nuntuk primality dengan membuat nkarakter string panjang dan mengujinya terhadap regex benar-benar mengerikan?
ninjalj

Jawaban:

6

Perl 5.10 (perl -E), 65 karakter

Setengah kredit (setidaknya) harus ke @J B.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
ninjalj
sumber
bagus! regex tes utama!
Ming-Tang
ya, saya mempelajarinya di stackoverflow.com/questions/3543811/code-golf-happy-primes
ninjalj
Sepertinya Anda dapat menyimpan beberapa karakter dengan regex yang dikutip (+2 untuk qr, -4 karena tidak memerlukan pembatas nanti).
Anon.
Sebenarnya, itu bekerja tanpa qr. LMGTFY: 81 karakter$m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"
JB
Babak kedua, memperhitungkan kedua pertandingan pola (66 karakter):perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}'
JB
12

Mathematica , 19

#~NextPrime~{-1,1}&
Tuan Wisaya
sumber
sangat pandai: 0)
Dr. belisarius
10

Mathematica: 28 karakter

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

Pemakaian

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
Belisarius
sumber
3

Python - 93

Berdasarkan jawaban oleh fR0DDY . Saya pada dasarnya menggabungkan baris 4 dan 5, dan memperpendek garis 2 dengan menggunakan metode yang berbeda.

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

Python 116 111 109 Karakter 

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
sumber
1
gunakanf=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))
st0le
@ fR0DDY, bukannya menggunakan 3 baris pertama n=input()-1dan m=n+2, menghemat 3 karakter ... saya pikir.
st0le
dan mungkin Anda bisa menggantinya not(all(...))dengan any(...)membalik boolean
st0le
Anda tidak menghitung garis baru. Hitungan sebenarnya adalah 108.
JPvdMerwe
1
Selain itu, harap hitung baris baru dalam jumlah karakter Anda. -1 untuk menipu orang lain.
moinudin
2

J, 22 karakter

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

Contoh

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

Python, 116 139 karakter (indentasi ganda adalah tab-char)

Gunakan Saringan Eratosthenes yang baik

Suntingan dan (terima kasih TON @JPvdMerwe). Harus bekerja dengan bilangan prima sekarang.

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

Asli

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.
sumber
-1 Untuk tidak menghitung spasi putih PERLU .
JPvdMerwe
@JPvdMerwe Kesalahan saya, saya baru di sini, dan saya menyadari bahwa saya mungkin telah menggunakan metrik yang salah dari editor saya.
Doug T.
@JPvDMerkami juga berterima kasih atas bantuan untuk pengeditan
Doug T.
@DougT keren semua orang membuat kesalahan :) +1 Untuk membalikkan suara saya, pastikan lain kali.
JPvdMerwe
Salah satu trik yang bisa Anda lakukan adalah memindahkan garis 1-3 di bawah garis 4 dan ganti a=range(9999)dengan a=range(n). Juga di baris 2 Anda tidak perlu meneruskan ake lambda, Anda bisa menggunakannya. Ini harus banyak mencukur.
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 untuk menjalankan semua 9998 int mulai dari 3 hingga 10.000

Pengguna tidak diketahui
sumber
1

Jelly , 5 byte (tidak bersaing?)

Æp,Æn

Cobalah online!

Erik the Outgolfer
sumber
1

Swift 190 187 185 110

Swift sangat buruk dalam kode-golf, tetapi saya tetap mencobanya: D
Semakin pendek dan pendek ... (Terima kasih kepada @HermanLauenstein karena menghapus 75 byte)

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
sumber
-75 byte dengan banyak restrukturisasi 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)}(saya belum mengujinya dengan benar)
Herman L
Terima kasih @HermanLauenstein. Ini kode-golf pertama saya, jadi saya butuh bantuan :)
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)

CATATAN: PrimesModul ini ditulis oleh saya tetapi sudah ada sebelum pertanyaan ini diajukan. TIDAK ditulis untuk ini. Namun demikian, ini dianggap tidak adil, jadi di sini adalah versi yang diperbarui.

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
sumber
Saya tidak tahu bagaimana Anda bisa salah menghitung, tetapi sebenarnya:123
JPvdMerwe
Juga, @John kecuali modul sekarang menjadi bagian dari bahasa, untuk kepentingan keadilan Anda harus memasukkan kode. Tapi pujian pada kejujuran.
JPvdMerwe
Saya pikir itu curang untuk digunakan Primes; melawan semangat kode golf.
Thomas O
@ JPV: Hah. Ini adalah salah. Saya bertanya-tanya bagaimana itu terjadi.
John
@Thomas, @JPv: Saya telah memposting versi yang diperbarui tanpa impor.
John
0

C (gcc) , 98 byte

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

Cobalah online!

Versi program lengkap, C (gcc) , 116 byte

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

Cobalah online!

Kedua versi berasumsi bahwa kami tidak pernah menguji 1 untuk primality, yang hanya terjadi jika inputnya 2 atau lebih rendah, dalam hal ini outputnya tetap tidak akan ditentukan.

gastropner
sumber