# 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? Commented 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. Commented 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. Commented Feb 7, 2011 at 2:14
• @ninjalj Just to weed out absolutely awful algorithms. Commented 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? Commented Feb 17, 2011 at 18:38

## Mathematica, 19

#~NextPrime~{-1,1}&

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

## Mathematica: 28 chars

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


Usage

%[1259]
{1249, 1277}

%[121231313159]
{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! Commented Feb 7, 2011 at 2:19
• yeah, I learned about it at stackoverflow.com/questions/3543811/code-golf-happy-primes Commented 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). Commented 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
Commented 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
Commented 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:"+ Commented 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))) Commented 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. Commented Feb 7, 2011 at 13:41
• and maybe you can replace not(all(...)) by any(...) reversing the booleans Commented Feb 7, 2011 at 13:45
• You don't count new lines. Actual count is 108. Commented Feb 7, 2011 at 21:01
• Also, please count newlines in your character count. -1 for deceiving others. Commented 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) Commented Apr 2, 2018 at 8:49
• Thanks @HermanLauenstein. It's my first code-golf, so I can need every help :) Commented 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. Commented 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. Commented Feb 7, 2011 at 21:10
• @JPvDMerwe also thanks for the help on the edits Commented Feb 7, 2011 at 21:12
• @DougT cool everyone makes a mistake :) +1 To reverse my down vote, just make sure next time. Commented 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. Commented 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 Commented 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. Commented Feb 8, 2011 at 5:51
• I think it cheating to use Primes; against the spirit of code golf. Commented Feb 8, 2011 at 8:05
• @JPv: Huh. It was wrong. I wonder how that happened.
– John
Commented Feb 8, 2011 at 18:25
• @Thomas, @JPv: I have posted an updated version without the import.
– John
Commented 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! Commented 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