17
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 32-bit number overflows, not buffer overflows, I guess. \$\endgroup\$ – user unknown Jan 14 '12 at 1:29
  • \$\begingroup\$ Whoops, meant "integer overflow". Brain went on autopilot. \$\endgroup\$ – Mr. Llama Jan 16 '12 at 14:57

31 Answers 31

11
\$\begingroup\$

J, 17

*/<:$&q:(<:,],>:)

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

   */<:$&q:(<:,],>:) 7
0
   */<:$&q:(<:,],>:) 8
0
   */<:$&q:(<:,],>:) 15
3
\$\endgroup\$
  • \$\begingroup\$ */0 p:<:,],>: is shorter and a proper (lambda) function is ([:*/0 p:<:,],>:) \$\endgroup\$ – randomra Jul 9 '13 at 10:40
9
\$\begingroup\$

Haskell, 47 characters

f n=any(\k->all((>0).mod k)[2..k-1])[n-1..n+1]
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – stranac Jan 14 '12 at 0:14
  • \$\begingroup\$ @stranac Awesome. Thank you very much. \$\endgroup\$ – Kris Harper Jan 14 '12 at 1:12
  • 3
    \$\begingroup\$ 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]) \$\endgroup\$ – Nabb Jan 14 '12 at 3:35
  • \$\begingroup\$ @Nabb Very nice. Well done. \$\endgroup\$ – Kris Harper Jan 14 '12 at 4:30
5
\$\begingroup\$

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])
\$\endgroup\$
  • \$\begingroup\$ You can remove the for loop and build it into the regexp by testing "1"*(n+1) but starting with ^1?1? instead. \$\endgroup\$ – Howard Jan 20 '12 at 15:11
4
\$\begingroup\$

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)

g=->q{(q-1..q+1).any?{|n|(2..n-1).all?{|d|n%d>0}}}

Coffeescript (53)

p=(q)->[q-1..q+1].some (n)->[2..n-1].every (d)->n%d>0
\$\endgroup\$
  • \$\begingroup\$ <pedantic> It should be "proc" not "lambda"</pedantic> ;-) \$\endgroup\$ – Doorknob Dec 27 '13 at 14:47
3
\$\begingroup\$

The boring Mathematica, 35 solution!

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

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:

p(n,q,r){for(r=0,q=2;q<n;)r|=!(n%q++);return!r;}
main(int n,int**m){putchar(48|p(n=atoi(*++m))|p(n-1)|p(n+1));}
\$\endgroup\$
  • \$\begingroup\$ You could save 2 chars with main(n,m)int**m;. \$\endgroup\$ – Ilmari Karonen Jan 17 '12 at 18:02
  • \$\begingroup\$ ...and besides, the challenge says "code-golf a function". \$\endgroup\$ – Ilmari Karonen Jan 17 '12 at 18:04
3
\$\begingroup\$

Mathematica, 24 bytes

Don't know why this old post showed up in my list today, but I realized Mathematica is competitive here.

Or@@PrimeQ/@{#-1,#,#+1}&

Unnamed function taking an integer argument and returning True or False. Direct implementation.

\$\endgroup\$
  • \$\begingroup\$ PrimeQ threads over lists, so Or@@PrimeQ@{#-1,#,#+1}& (or Or@@PrimeQ[#+{-1,0,1}]&) also works, for -1 byte. (Although, I guess I don't know if PrimeQ threaded over lists in 2012.) \$\endgroup\$ – Misha Lavrov Nov 12 '18 at 2:19
3
\$\begingroup\$

Stax, 6 bytes

Ç▀<╝ºΩ

Run and debug it

Explanation (unpacked):

;v:Pv<! Full program, implicit input  Example: 7
;v      Copy input and decrement               7 6
  :P    Next prime                             7 7
    v   Decrement                              7 6
     <! Check if input is >= result            1
\$\endgroup\$
2
\$\begingroup\$

JavaScript (71 73 80)

n=prompt(r=0);for(j=n-2;p=j++<=n;r|=p)for(i=1;++i<j;)p=j%i?p:0;alert(r)

Demo: http://jsfiddle.net/ydsxJ/3/

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

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

Regex (ECMAScript), 20 bytes

^x?x?(?!(x+)(x\1)+$)

Try it online!

The above version does not correctly handle zero, but that only takes 1 extra byte:

^x?x?(?!(x+)(x\1)+$)x

As an added bonus, here's a version that gives a return match of 1 for one less than a prime, 2 for prime, and 3 for one more than a prime:

^x?x??(?!(x+)(x\1)+$)x

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The range the question speaks about it is "between 2^0 and 2^20" so 1..2^20 so 0 there isn't... \$\endgroup\$ – RosLuP Feb 3 at 8:24
  • \$\begingroup\$ @RosLuP Which is exactly why my primary answer is 20 bytes and doesn't handle 0 correctly. I find value in going beyond the precise specifications of the question and giving more robust answers, along with the answer that minimally matches the question's spec. \$\endgroup\$ – Deadcode Feb 3 at 8:34
  • \$\begingroup\$ Sometimes I do the same (write 'unnecessary' test) but this seems goes against codegolf way of thinking, and people that write them are not considered "serious"... \$\endgroup\$ – RosLuP Feb 3 at 8:34
  • 1
    \$\begingroup\$ @RosLuP But what's the harm, as long as I give the minimal answer as my primary answer? And can you give any examples of people who actually think that way? I could understand it if I gave my only answer as the robust one, but I'm not doing that. \$\endgroup\$ – Deadcode Feb 3 at 8:35
1
\$\begingroup\$

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++){
        if(i==r-1)break;
        if(r%i==0)r+=i=1;
    }
    return r-q;     
}
\$\endgroup\$
  • \$\begingroup\$ I'm not entirely sure, but I think you could remove the if(i==r-1)break; and change the middle of the for loop from i<r to i<r-1. It would bring you down to 82. \$\endgroup\$ – Ciaran_McCarthy May 3 '18 at 7:51
1
\$\begingroup\$

GolfScript: 26

)0\{.:i,{i\%!},,2=@|\(}3*;

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.

\$\endgroup\$
1
\$\begingroup\$

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));}
\$\endgroup\$
  • \$\begingroup\$ I don't think this works with 1 or 2 as input \$\endgroup\$ – Ben Reich Dec 29 '13 at 4:30
  • \$\begingroup\$ @BenReich It didn't. I had to add ten chars to fix it :( \$\endgroup\$ – Steve Clanton Dec 31 '13 at 16:34
1
\$\begingroup\$

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.

{(3,f+:mp:|}

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:

(3,f+:mp:|
(          "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.";
\$\endgroup\$
1
\$\begingroup\$

F#, 68 bytes (non-competing)

let p n=Seq.forall(fun x->n%x>0){2..n-1}
let m n=p(n-1)||p n||p(n+1)

Try it online!

This is why I love code golf. I'm still very green with F# but I learn so much about how the language works and what it can do from these kinds of challenges.

\$\endgroup\$
  • \$\begingroup\$ Why is it non-competing? \$\endgroup\$ – Nit May 3 '18 at 14:47
  • 1
    \$\begingroup\$ Because I'm not sure if I'm using anything in F# today that wasn't around when the question was asked in 2012. I admit it's pedantic - even paranoid. But I write pharmaceutical software for a living. Paranoia is healthy. ;) \$\endgroup\$ – Ciaran_McCarthy May 3 '18 at 15:37
  • 1
    \$\begingroup\$ Look at F#'s version table in Wikipedia. Depending on the version you need, it may be older than the question. \$\endgroup\$ – yeti May 3 '18 at 18:24
1
\$\begingroup\$

APL (Dyalog Classic), 20 bytes

0∊¯1 0 1∘+∊(∘.×⍨1↓⍳)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Retina, 22 bytes

$
1
^1?1?(?!(11+)\1+$)

Try it online!

Takes unary as input

\$\endgroup\$
  • \$\begingroup\$ A pure regex Retina solution beats this by 2 bytes. \$\endgroup\$ – Deadcode Feb 3 at 7:39
  • \$\begingroup\$ Looks like this was what Howard had in mind. \$\endgroup\$ – Neil Feb 5 at 10:42
1
\$\begingroup\$

Java 8, 83 bytes

n->n==1|p(n-1)+p(n)+p(n+1)>0int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return--n;}

Returns true / false as truthy/falsey values.

Try it online.

Explanation:"

n->                    // Method with integer parameter and boolean return-type
  n==1                 //  Return whether the input is 1 (edge-case)
  |p(n-1)+p(n)+p(n+1)>0//  Or if the sum of `n-1`, `n`, and `n+1` in method `p(n)` is not 0

int p(int n){          // Separated method with integer as both parameter and return-type
  for(int i=2;i<n;     //  Loop `i` in the range [2, `n`)
    n=n%i++<1?         //   If `n` is divisible by `i`
       0               //    Change `n` to 0
      :                //   Else:
       n);             //    Leave `n` as is
                       //  (After the loop `n` is either 0, 1, or unchanged,
                       //   if it's unchanged it's a prime, otherwise not)
  return--n;}          //  Return `n` minus 1

So int p(int n) will result in -1 for n=0 and non-primes, and will result in n-1 for n=1 or primes. Since p(0)+p(1)+p(2) will become -1+0+1 = 0 and would return false (even though 2 is a prime), the n=1 is an edge case using this approach.


A single loop without separated method would be 85 bytes:

n->{int f=0,j=2,i,t;for(;j-->-1;f=t>1?1:f)for(t=n+j,i=2;i<t;t=t%i++<1?0:t);return f;}

Returns 1 / 0 as truthy/falsey values.

Try it online.

Explanation:

n->{              // Method with integer as both parameter and return-type
  int f=0,        //  Result-integer, starting at 0 (false)
      j=2,i,      //  Index integers
      t;          //  Temp integer
  for(;j-->-1;    //  Loop `j` downwards in range (2, -1]
      f=          //    After every iteration: Change `f` to:
        t>1?      //     If `t` is larger than 1 (`t` is a prime):
         1        //      Change `f` to 1 (true)
        :         //     Else:
         f)       //      Leave `f` the same
    for(t=n+j,    //   Set `t` to `n+j`
        i=2;i<t;  //   Inner loop `i` in the range [2, t)
      t=t%i++<1?  //    If `t` is divisible by `i`:
         0        //     Change `t` to 0
        :         //    Else:
         t);      //     Leave `t` the same
                  //   (If `t` is still the same after this inner loop, it's a prime;
                  //   if it's 0 or 1 instead, it's not a prime)
  return f;}      //  Return the result-integer (either 1/0 for true/false respectively)
\$\endgroup\$
1
\$\begingroup\$

Japt, 7 bytes

´Uô2 dj
´Uô2    // Given the range [U-1..U+1],
     dj // sing "Daddy DJ", uh, I mean, check if any are a prime.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 68 chars

f=function(n){library(gmp);i=isprime;ifelse(i(n-1)|i(n)|i(n+1),1,0)}

Usage (1 for TRUE, 0 for FALSE):

f(7)
[1] 1
f(8)
[1] 1
f(15)
[1] 0
\$\endgroup\$
  • 1
    \$\begingroup\$ 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)? \$\endgroup\$ – Ry- Jul 9 '13 at 2:07
  • \$\begingroup\$ You are right: g=function(n){library(gmp);i=isprime;i(n-1)|i(n)|i(n+1)} - down to 56 characters! ;-) \$\endgroup\$ – Paolo Sep 4 '13 at 12:50
0
\$\begingroup\$

C++

k=3;cin>>i;i--;
while(k)
{l[k]=0;
  for(j=2;j<i;j++)
   if(!(i%j))
     l[k]++;
  k--;
  i++;
}
if(!l[1]|!l[2]|!l[3])
     cout<<"1";
else cout<<"0";
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – dmckee Jan 31 '12 at 20:48
0
\$\begingroup\$

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

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

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

\$\endgroup\$
0
\$\begingroup\$

Ruby, 47 chars but very readable

require'Prime'
f=->x{[x-1,x,x+1].any? &:prime?}
\$\endgroup\$
0
\$\begingroup\$

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

Forth (gforth), 104 bytes

: p dup 1 > if 1 over 2 ?do over i mod 0> * loop else 0 then nip ;
: f dup 1- p over 1+ p rot p + + 0< ;

Try it online!

Explanation

Prime check (p)

dup 1 > if          \ if number to check if greater than 1
   1 over 2 ?do     \ place a 1 on the stack to act as a boolean and loop from 2 to n
      over i  mod   \ take the modulo of n and i
      0> *          \ check if greater than 0 (not a divisor) and multiply result by boolean
   loop             \ end the loop, result will be -1 if no divisor was found (prime)
else                \ if n is less than 2
   0                \ put 0 on the stack (not prime)
then                \ end the loop
nip                 \ drop n from the stack

Main Function (f)

dup 1- p             \ get n-1 and check if prime
over 1+ p            \ get n+1 and check if prime
rot p                \ rotate stack to put n on top and check if prime
+ + 0<               \ add the three results and check if less than 0 (at least 1 was prime)
\$\endgroup\$
0
\$\begingroup\$

Julia 0.4, 23 bytes

n->any(isprime,n-1:n+1)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 5 bytes

‘r’ẒẸ

Try it online!

How it works

‘r’ẒẸ    Monadic main link. Input: integer n
‘r’      Generate range n-1..n+1
   ẒẸ    Is any of them a prime?
\$\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.