11
\$\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\$
7
  • 3
    \$\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, 2011 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, 2011 at 1:22
  • 2
    \$\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, 2011 at 2:14
  • \$\begingroup\$ @ninjalj Just to weed out absolutely awful algorithms. \$\endgroup\$
    – Thomas O
    Feb 17, 2011 at 13:00
  • 5
    \$\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, 2011 at 18:38

18 Answers 18

15
\$\begingroup\$

Mathematica, 19

#~NextPrime~{-1,1}&
\$\endgroup\$
1
  • \$\begingroup\$ very clever :0) \$\endgroup\$ Jul 31, 2012 at 12:13
11
\$\begingroup\$

Mathematica: 28 chars

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

Usage

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
\$\endgroup\$
7
\$\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\$
5
  • \$\begingroup\$ nice! the prime test regex! \$\endgroup\$
    – Ming-Tang
    Feb 7, 2011 at 2:19
  • \$\begingroup\$ yeah, I learned about it at stackoverflow.com/questions/3543811/code-golf-happy-primes \$\endgroup\$
    – ninjalj
    Feb 7, 2011 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, 2011 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, 2011 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, 2011 at 9:47
4
\$\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\$
4
\$\begingroup\$

J, 22 characters

(_4&p:,4&p:)(".stdin)_
\$\endgroup\$
1
  • \$\begingroup\$ 9 years old but hey... :) _4 4 p:"+ \$\endgroup\$
    – Jonah
    Apr 17, 2021 at 5:46
3
\$\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\$
8
  • 1
    \$\begingroup\$ use f=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13))) \$\endgroup\$
    – st0le
    Feb 7, 2011 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, 2011 at 13:41
  • \$\begingroup\$ and maybe you can replace not(all(...)) by any(...) reversing the booleans \$\endgroup\$
    – st0le
    Feb 7, 2011 at 13:45
  • \$\begingroup\$ You don't count new lines. Actual count is 108. \$\endgroup\$
    – JPvdMerwe
    Feb 7, 2011 at 21:01
  • 1
    \$\begingroup\$ Also, please count newlines in your character count. -1 for deceiving others. \$\endgroup\$
    – moinudin
    Feb 7, 2011 at 21:02
3
+100
\$\begingroup\$

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().

\$\endgroup\$
3
\$\begingroup\$

Jelly, 5 bytes

Æp,Æn

Try it online!

\$\endgroup\$
2
\$\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\$
2
  • \$\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, 2018 at 8:49
  • \$\begingroup\$ Thanks @HermanLauenstein. It's my first code-golf, so I can need every help :) \$\endgroup\$ Apr 2, 2018 at 9:53
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\$
11
  • 1
    \$\begingroup\$ -1 For not counting NECESSARY white space. \$\endgroup\$
    – JPvdMerwe
    Feb 7, 2011 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, 2011 at 21:10
  • \$\begingroup\$ @JPvDMerwe also thanks for the help on the edits \$\endgroup\$
    – Doug T.
    Feb 7, 2011 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, 2011 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, 2011 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\$
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\$
7
  • \$\begingroup\$ I don't know how you managed to get your count wrong but it's actually: 123 \$\endgroup\$
    – JPvdMerwe
    Feb 8, 2011 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, 2011 at 5:51
  • \$\begingroup\$ I think it cheating to use Primes; against the spirit of code golf. \$\endgroup\$
    – Thomas O
    Feb 8, 2011 at 8:05
  • \$\begingroup\$ @JPv: Huh. It was wrong. I wonder how that happened. \$\endgroup\$
    – John
    Feb 8, 2011 at 18:25
  • \$\begingroup\$ @Thomas, @JPv: I have posted an updated version without the import. \$\endgroup\$
    – John
    Feb 8, 2011 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\$

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

C (gcc), 98 89 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), 116 107 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!

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Nice one! \$\endgroup\$
    – gastropner
    Nov 20, 2020 at 16:59
0
\$\begingroup\$

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
\$\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.