Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Your challenge, should you chose to accept it, is to code-golf a function that returns true or false (or some similar meaningful representation of yes and no) if a number meets the following criteria:

  1. The integer itself is a prime number OR
  2. Either of its neighbor integers are prime

For example:
An input of 7 would return True.
An input of 8 would also return True.
An input of 15 would return False. (Neither 14, 15, or 16 are prime)

The input must be able to return correctly for numbers between 2^0 and 2^20 inclusive, so there's no need to worry about sign issues or integer overflows.

share|improve this question
32-bit number overflows, not buffer overflows, I guess. – user unknown Jan 14 '12 at 1:29
Whoops, meant "integer overflow". Brain went on autopilot. – Mr. Llama Jan 16 '12 at 14:57

19 Answers 19

up vote 10 down vote accepted

J, 17


Returns booleans encoded as process return codes: zero for true, nonzero for false. Sample use:

   */<:$&q:(<:,],>:) 7
   */<:$&q:(<:,],>:) 8
   */<:$&q:(<:,],>:) 15
share|improve this answer
*/0 p:<:,],>: is shorter and a proper (lambda) function is ([:*/0 p:<:,],>:) – randomra Jul 9 '13 at 10:40

Haskell, 47 characters

f n=any(\k->all((>0).mod k)[2..k-1])[n-1..n+1]
share|improve this answer

Python 85 80

def f(n):g=lambda n:all(n%i!=0for i in range(2,n));return g(n)or g(n-1)or g(n+1)

First time on Code Golf so there's probably some tricks I'm missing.

share|improve this answer
You can remove the []. all will be more than happy to work with a generator expression. If you don't mind your code being ugly, you can also remove the spaces between 0 and for, and ) and or. – stranac Jan 14 '12 at 0:14
@stranac Awesome. Thank you very much. – Kris Harper Jan 14 '12 at 1:12
Made a few straightforward changes, hopefully it still works: f=lambda n:any(all(m%i for i in range(2,m))for m in[n,n-1,n+1]) – Nabb Jan 14 '12 at 3:35
@Nabb Very nice. Well done. – Kris Harper Jan 14 '12 at 4:30

Not a real contender in code shortness by any means, but still submitting since determining primeness by regular expression is twisted in many ways!

Python (2.x), 85 characters

import re
f=lambda n:any(not re.match(r"^1?$|^(11+?)\1+$","1"*x)for x in[n,n-1,n+1])
share|improve this answer
You can remove the for loop and build it into the regexp by testing "1"*(n+1) but starting with ^1?1? instead. – Howard Jan 20 '12 at 15:11

Ruby (55, or 50 as lambda)

def f q;(q-1..q+1).any?{|n|(2..n-1).all?{|d|n%d>0}};end

or as lambda (use g[23] to call it)


Coffeescript (53)

p=(q)->[q-1..q+1].some (n)->[2..n-1].every (d)->n%d>0
share|improve this answer
<pedantic> It should be "proc" not "lambda"</pedantic> ;-) – Doorknob Dec 27 '13 at 14:47

C, 112 82 72 characters

Following Ilmari Karonen's comment, saved 30 chars by removing main, now P returns true/false. Also replaced loop with recursion, and some more tweaks.

p(n,q){return++q==n||n%q&&p(n,q);}P(n){return p(-~n,1)|p(n,1)|p(~-n,1);}

Original version:

main(int n,int**m){putchar(48|p(n=atoi(*++m))|p(n-1)|p(n+1));}
share|improve this answer
You could save 2 chars with main(n,m)int**m;. – Ilmari Karonen Jan 17 '12 at 18:02
...and besides, the challenge says "code-golf a function". – Ilmari Karonen Jan 17 '12 at 18:04

The boring Mathematica, 35 solution!

share|improve this answer
At least you may golf it into Or@@PrimeQ/@{n-1,n,n+1}. – Howard Jan 14 '12 at 10:04
This is not a function. – Martin Ender Feb 20 '15 at 18:24
@MartinBüttner: I don’t know Mathematica, sorry. – Ryan O'Hara Feb 20 '15 at 21:33
Using Howard's version, Or@@PrimeQ@{#-1,#,#+1}& (the slash in his code isn't needed) – Martin Ender Feb 20 '15 at 21:34

JavaScript (71 73 80)



Edit 1: Change for(i=2;i<j;i++) to for(i=1;++i<j;) (thanks @minitech). Convert if statement to ternary. Moved r|=p and p=1 into outer for to eliminate inner braces. Saved 7 characters.

Edit 2: Combine p=1 and j++<=n to p=j++<=n, save 2 chars (thanks @ugoren).

share|improve this answer
You can use for(i=1;++i<j;) instead of for(i=2;i<j;i++) to save 1 more character. – Ryan O'Hara Jan 14 '12 at 1:18
@minitech: !j%i won't work because of precedence. A working alternative is j%i<1. – Nabb Jan 14 '12 at 3:37
@Nabb: Wow, you're right. That's silly. – Ryan O'Hara Jan 14 '12 at 3:40
How about p=j++<=n? If Javascript is like C here, it should work. – ugoren Jan 18 '12 at 11:34
@ugoren: Looks like it worked, thanks! – mellamokb Jan 18 '12 at 16:07

GolfScript: 26


Explanation: The innermost block {.:i,{i\%!},,2=@|\(} determines if the top of the stack is prime by checking if there are exactly 2 factors less than the top of the stack. It then disjuncts this with the second item on the stack, which holds the state of whether a prime has been seen yet. Finally, it decrements the number on the top of the stack.

Start by incrementing the input, initializing the prime-seen state, and repeat the block 3 times. Since this will decrement twice, but we started by incrementing, this will cover n+1 and n-1.

share|improve this answer

C#, 87 97 chars

bool p(int q){return new[]{q-1,q,q+1}.Any(x=>Enumerable.Range(2,Math.Abs(x-2)).All(y=>x%y!=0));}
share|improve this answer
I don't think this works with 1 or 2 as input – Ben Reich Dec 29 '13 at 4:30
@BenReich It didn't. I had to add ten chars to fix it :( – Steve Clanton Dec 31 '13 at 16:34

CJam, 12 bytes

CJam is much younger than this challenge, so this answer is not eligible for the green checkmark (which should be updated to randomra's answer anyway). However, golfing this was actually quite fun - I started at 17 bytes and then changed my approach completely three times, saving one or two bytes each time.


This is a block, the closest equivalent to a function in CJam, which expects the input on the stack, and leaves a 1 (truthy) or 0 (falsy) on the stack.

Test it here.

Here is how it works:

(          "Decrement the input N.";
 3,        "Push an array [0 1 2].";
   f+      "Add each of those to N-1, to get [N-1 N N+1].";
     :mp   "Test each each element for primality, yielding 0 or 1.";
        :| "Fold bitwise OR onto the list, which gives 1 if any of them was 1.";
share|improve this answer

R, 68 chars


Usage (1 for TRUE, 0 for FALSE):

[1] 1
[1] 1
[1] 0
share|improve this answer
I don’t really know how R works, but could you just do i(n-1)|i(n)|i(n+1) instead of ifelse(i(n-1)|i(n)|i(n+1),1,0)? – Ryan O'Hara Jul 9 '13 at 2:07
You are right: g=function(n){library(gmp);i=isprime;i(n-1)|i(n)|i(n+1)} - down to 56 characters! ;-) – Paolo Sep 4 '13 at 12:50


else cout<<"0";
share|improve this answer
Welcome to CodeGold.SE. If you look at the other answers you'll notice a common format used for answers to [code-golf] questions. You might want to apply it to your answers as well. – dmckee Jan 31 '12 at 20:48

Q, 43 chars 36

{any min each a mod 2_'til each a:x+-1 0 1}
{any(min')a mod 2_'(til')a:x+-1 0 1}
share|improve this answer

J, 16 chars

   (_2&<@-4 p:]-2:)

   (_2&<@-4 p:]-2:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
share|improve this answer

C#, 96

It returns -1,0,1 for true, anything else is false.

Any suggestions to make it shorter would be wonderful!

int p(int q){var r=q-1;for(var i=2;i<r&r<q+2;i++){if(i==r-1)break;if(r%i==0)r+=i=1;}return r-q;}

Expanded form:

int p(int q){
    var r=q-1;
    for(var i=2;i<r&r<q+2;i++){
    return r-q;     
share|improve this answer

Python, 69 67 chars

any(all(i%j for j in range(2,i))for i in range(input()-1,8**7)[:3])

8**7 > 2**20 while being slightly shorter to write

share|improve this answer

Ruby, 47 chars but very readable

f=->x{[x-1,x,x+1].any? &:prime?}
share|improve this answer

C++ 97

ugoren seems to have beat me to the clever solution. So he's a shortish version on the loop three times approach:

P(int k){int j=1;for(int i=2;i<k;){j=k%i++&&j;}return j;}
a(int b){return P(b)|P(b+1)|P(b-1);}
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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