9
\$\begingroup\$

Write a program which takes an input (which may or may not be prime), and lists the immediate prime following and preceding it.

Example input:

1259

Example output:

1249 1277

Shortest program wins. Must execute within 10 seconds on a modern desktop PC. Inputs will be limited to 10,000 maximum.

\$\endgroup\$
  • 2
    \$\begingroup\$ It seems somewhat odd to list a time limit without also limiting the range of possible inputs. Are we required to find several-thousand-digit primes within ten seconds? \$\endgroup\$ – Anon. Feb 7 '11 at 1:20
  • \$\begingroup\$ @Anon. Assume I will not give ridiculous inputs, but the program must be somewhat optimised. I have clarified the question text. \$\endgroup\$ – Thomas O Feb 7 '11 at 1:22
  • \$\begingroup\$ my one-liner is anything but optimal, but it runs in ~1s for an input of 10000. You have to try really hard to need 10s. \$\endgroup\$ – ninjalj Feb 7 '11 at 2:14
  • \$\begingroup\$ @ninjalj Just to weed out absolutely awful algorithms. \$\endgroup\$ – Thomas O Feb 17 '11 at 13:00
  • 3
    \$\begingroup\$ so you don't consider testing a number n for primality by creating a string n characters long and testing that against a regex absolutely awful? \$\endgroup\$ – ninjalj Feb 17 '11 at 18:38

15 Answers 15

6
\$\begingroup\$

Perl 5.10 (perl -E), 65 chars

Half the credit (at least) should go to @J B.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
\$\endgroup\$
  • \$\begingroup\$ nice! the prime test regex! \$\endgroup\$ – Ming-Tang Feb 7 '11 at 2:19
  • \$\begingroup\$ yeah, I learned about it at stackoverflow.com/questions/3543811/code-golf-happy-primes \$\endgroup\$ – ninjalj Feb 7 '11 at 2:23
  • \$\begingroup\$ Seems like you could save a couple of characters with a quoted regex (+2 for the qr, -4 for not needing the delimiters later). \$\endgroup\$ – Anon. Feb 7 '11 at 4:00
  • \$\begingroup\$ Actually, it works without qr. LMGTFY: 81 chars $m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/" \$\endgroup\$ – J B Feb 7 '11 at 9:38
  • \$\begingroup\$ Second round, factoring both pattern matches (66 chars): perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}' \$\endgroup\$ – J B Feb 7 '11 at 9:47
11
\$\begingroup\$

Mathematica, 19

#~NextPrime~{-1,1}&
\$\endgroup\$
  • \$\begingroup\$ very clever :0) \$\endgroup\$ – Dr. belisarius Jul 31 '12 at 12:13
10
\$\begingroup\$

Mathematica: 28 chars

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

Usage

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
\$\endgroup\$
3
\$\begingroup\$

Python - 93

Based on answer by fR0DDY. I basically merged lines 4 and 5, and shortened line 2 by using a different method.

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
\$\endgroup\$
2
\$\begingroup\$

Python 116 111 109 Characters

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
\$\endgroup\$
  • 1
    \$\begingroup\$ use f=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13))) \$\endgroup\$ – st0le Feb 7 '11 at 9:45
  • \$\begingroup\$ @fR0DDY, instead of the first 3 lines use n=input()-1 and m=n+2, saves 3 chars...i think. \$\endgroup\$ – st0le Feb 7 '11 at 13:41
  • \$\begingroup\$ and maybe you can replace not(all(...)) by any(...) reversing the booleans \$\endgroup\$ – st0le Feb 7 '11 at 13:45
  • \$\begingroup\$ You don't count new lines. Actual count is 108. \$\endgroup\$ – JPvdMerwe Feb 7 '11 at 21:01
  • 1
    \$\begingroup\$ Also, please count newlines in your character count. -1 for deceiving others. \$\endgroup\$ – marcog Feb 7 '11 at 21:02
2
\$\begingroup\$

J, 22 characters

(_4&p:,4&p:)(".stdin)_
\$\endgroup\$
1
\$\begingroup\$

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..]

Example

Main> p 1259
(1249,1277)
\$\endgroup\$
1
\$\begingroup\$

Python, 116 139 chars (double indent is tab-char)

Uses good ole Sieve of Eratosthenes

Edits and (thanks a TON @JPvdMerwe). Should work with primes now.

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
\$\endgroup\$
  • \$\begingroup\$ -1 For not counting NECESSARY white space. \$\endgroup\$ – JPvdMerwe Feb 7 '11 at 21:09
  • \$\begingroup\$ @JPvdMerwe My fault, I'm new here, and I realized I may have used the wrong metric from my editor. \$\endgroup\$ – Doug T. Feb 7 '11 at 21:10
  • \$\begingroup\$ @JPvDMerwe also thanks for the help on the edits \$\endgroup\$ – Doug T. Feb 7 '11 at 21:12
  • \$\begingroup\$ @DougT cool everyone makes a mistake :) +1 To reverse my down vote, just make sure next time. \$\endgroup\$ – JPvdMerwe Feb 7 '11 at 21:15
  • \$\begingroup\$ One trick you can do is to move lines 1-3 below line 4 and replace a=range(9999) with a=range(n). Also in line 2 you don't need to pass a to the lambda, you can just use it. This should shave off a lot. \$\endgroup\$ – JPvdMerwe Feb 7 '11 at 21:25
1
\$\begingroup\$

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 to run all 9998 ints from 3 to 10.000

\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes (non-competing?)

Æp,Æn

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Swift 190 187 185 110

Swift is very bad in code-golf, but I tried it anyway :D
It's getting shorter and shorter...(Thanks to @HermanLauenstein for removing 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)}
\$\endgroup\$
  • \$\begingroup\$ -75 bytes with a lot of restructuring 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)} (I haven't tested it properly yet) \$\endgroup\$ – Herman L Apr 2 '18 at 8:49
  • \$\begingroup\$ Thanks @HermanLauenstein. It's my first code-golf, so I can need every help :) \$\endgroup\$ – Josef Zoller Apr 2 '18 at 9:53
0
\$\begingroup\$

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: The Primes module was written by me but it existed before this question was asked. It was NOT written for this. Nevertheless, this was deemed unfair, so here is the updated 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)
\$\endgroup\$
  • \$\begingroup\$ I don't know how you managed to get your count wrong but it's actually: 123 \$\endgroup\$ – JPvdMerwe Feb 8 '11 at 5:48
  • \$\begingroup\$ Also, @John unless the module is now part of the language, in the interest of fairness you should include the code. But Kudos on the honesty. \$\endgroup\$ – JPvdMerwe Feb 8 '11 at 5:51
  • \$\begingroup\$ I think it cheating to use Primes; against the spirit of code golf. \$\endgroup\$ – Thomas O Feb 8 '11 at 8:05
  • \$\begingroup\$ @JPv: Huh. It was wrong. I wonder how that happened. \$\endgroup\$ – John Feb 8 '11 at 18:25
  • \$\begingroup\$ @Thomas, @JPv: I have posted an updated version without the import. \$\endgroup\$ – John Feb 8 '11 at 18:26
0
\$\begingroup\$

Stax, 7 bytes

èëïy▌Ü╚

Run and debug it

ASCII equivalent:

^:Px:pLJ

Built-ins.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 79 bytes

f=(n,d)=>d?p(n)?n:f(n+d,d):[f(n-1,-1),f(n+1,1)]
p=(n,i=1)=>++i*i>n||n%i&&p(n,i)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

Try it online!

Full program version, 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);}

Try it online!

Both versions assume that we never test 1 for primality, which only happens if the input is 2 or lower, in which case the output would be undefined anyway.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.