# Output nearby primes

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.

-
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? – Anon. Feb 7 '11 at 1:20
@Anon. Assume I will not give ridiculous inputs, but the program must be somewhat optimised. I have clarified the question text. – Thomas O Feb 7 '11 at 1:22
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. – ninjalj Feb 7 '11 at 2:14
@ninjalj Just to weed out absolutely awful algorithms. – Thomas O Feb 17 '11 at 13:00
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? – ninjalj Feb 17 '11 at 18:38
show 1 more comment

## 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}
``````
-
 nice! the prime test regex! – SHiNKiROU Feb 7 '11 at 2:19 yeah, I learned about it at stackoverflow.com/questions/3543811/code-golf-happy-primes – ninjalj Feb 7 '11 at 2:23 Seems like you could save a couple of characters with a quoted regex (+2 for the `qr`, -4 for not needing the delimiters later). – Anon. Feb 7 '11 at 4:00 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\$/"` – J B Feb 7 '11 at 9:38 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}'` – J B Feb 7 '11 at 9:47

## Mathematica: 28 chars

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

Usage

``````%[1259]
{1249, 1277}

%[121231313159]
{121231313129, 121231313191}
``````
-

## Mathematica, 19

``````#~NextPrime~{-1,1}&
``````
-
 very clever :0) – belisarius Jul 31 '12 at 12:13

## 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
``````
-

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

## J, 22 characters

``````(_4&p:,4&p:)(".stdin)_
``````
-

``````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)
``````
-

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
``````
-
 -1 For not counting NECESSARY white space. – JPvdMerwe Feb 7 '11 at 21:09 @JPvdMerwe My fault, I'm new here, and I realized I may have used the wrong metric from my editor. – Doug T. Feb 7 '11 at 21:10 @JPvDMerwe also thanks for the help on the edits – Doug T. Feb 7 '11 at 21:12 @DougT cool everyone makes a mistake :) +1 To reverse my down vote, just make sure next time. – JPvdMerwe Feb 7 '11 at 21:15 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. – JPvdMerwe Feb 7 '11 at 21:25

### 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)
``````

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

-

## 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)
``````
-
 I don't know how you managed to get your count wrong but it's actually: `123` – JPvdMerwe Feb 8 '11 at 5:48 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. – JPvdMerwe Feb 8 '11 at 5:51 I think it cheating to use `Primes`; against the spirit of code golf. – Thomas O Feb 8 '11 at 8:05 @JPv: Huh. It was wrong. I wonder how that happened. – John Feb 8 '11 at 18:25 @Thomas, @JPv: I have posted an updated version without the import. – John Feb 8 '11 at 18:26