# 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? Feb 7, 2011 at 1:20
• @Anon. Assume I will not give ridiculous inputs, but the program must be somewhat optimised. I have clarified the question text. Feb 7, 2011 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. Feb 7, 2011 at 2:14
• @ninjalj Just to weed out absolutely awful algorithms. Feb 17, 2011 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? Feb 17, 2011 at 18:38

## Mathematica, 19

#~NextPrime~{-1,1}&

• very clever :0) Jul 31, 2012 at 12:13

## Mathematica: 28 chars

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


Usage

%
{1249, 1277}

%
{121231313129, 121231313191}


## 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! Feb 7, 2011 at 2:19
• yeah, I learned about it at stackoverflow.com/questions/3543811/code-golf-happy-primes Feb 7, 2011 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). Feb 7, 2011 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, 2011 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, 2011 at 9:47

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


## J, 22 characters

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

• 9 years old but hey... :) _4 4 p:"+ Apr 17, 2021 at 5:46

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

# APL (Dyalog Extended), 6 bytes

¯4 4⍭⊢


Try it online!

I wish I knew a way to shorten this further.

¯4 and 4 when passed to ⍭ give the closest primes to the right argument(⊢).

# Jelly, 5 bytes

Æp,Æn


Try it online!

# Swift 190187185 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)}

• -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) Apr 2, 2018 at 8:49
• Thanks @HermanLauenstein. It's my first code-golf, so I can need every help :) Apr 2, 2018 at 9:53

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. Feb 7, 2011 at 21:09
• @JPvdMerwe My fault, I'm new here, and I realized I may have used the wrong metric from my editor. Feb 7, 2011 at 21:10
• @JPvDMerwe also thanks for the help on the edits Feb 7, 2011 at 21:12
• @DougT cool everyone makes a mistake :) +1 To reverse my down vote, just make sure next time. Feb 7, 2011 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. Feb 7, 2011 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 Feb 8, 2011 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. Feb 8, 2011 at 5:51
• I think it cheating to use Primes; against the spirit of code golf. Feb 8, 2011 at 8:05
• @JPv: Huh. It was wrong. I wonder how that happened.
– John
Feb 8, 2011 at 18:25
• @Thomas, @JPv: I have posted an updated version without the import.
– John
Feb 8, 2011 at 18:26

# Stax, 7 bytes

èëïy▌Ü╚


Run and debug it

ASCII equivalent:

^:Px:pLJ


Built-ins.

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

# Arn, 22 bytes

ét█ï▀¢│B¬Ÿ6├¼òa¡b←Æ╚ÑÕ


Try it!

# Explained

Unpacked: k:((v:#.^2):i)[v?--k v?(k+2

One of the major weaknesses of Arn (along with operator precedence lmao)

  :                     Assign variable
k                       with name of k
(                   Begin expression
(
:
v
#.        List of primes from 0 to
_     Variable initialized to STDIN; implied
^       exponentiated by
2     Literal two
)               End expression
:i                Index of
_               implied
)
[                       Begin sequence
v
?                     Indexed by
--k                 k minus 1
v
?
(
k
+                 Plus
2
)                   implied
]                       End of sequence; implied


# C (gcc), 9889 87 bytes

-9 bytes thanks to ceilingcat

N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}f(n){g(n,-1);g(n,1);}


Try it online!

# Full program version, C (gcc), 116107 105 bytes

-9 bytes thanks to ceilingcat

N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}main(n){scanf("%d",&n);g(n,-1);g(n,1);}


Try it online!

• @ceilingcat Nice one! Nov 20, 2020 at 16:59

# 05AB1E, 6 bytes

ÅMsÅN»


Try it online!

ÅMsÅN»  # full program
»  # join...
ÅM      # nearest prime less than...
# implicit input...
»  # with...
ÅN   # nearest prime greater than...
s     # implicit input...
»  # by a newline
# implicit output