Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Finding primes is a programming rite of passage and very frequently a first serious program someone crates (usually with trial division).

But primes alone are already worn out. A next far more interesting thing is to get the prime gaps: the so-far-longest gaps between consecutive primes. These are quite rare and "precious". A first few pairs and their differences are:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
...

My father used to calculate these by hand for fun up to 10k. Let's see how short a code you can get.

Rules:

  • no builtin functions for prime testing, prime generation or prime gaps
  • no retrieving http://oeis.org/A002386 or similar (I can smell you cheaters from far away :) )
  • no precomputed arrays
  • keep printing until your internal integer type fails on you

Lowest character count wins. +10 characters if you only print the gaps without the primes.

You can also show off versions with builtin functions if they are interesting. Be creative.

Clarification: you go through primes and you report every time you see a gap that is bigger than any gap that you have seen before. For instance, between 3 and 5, there is a gap 2 units wide. The gap between 5 and 7 is also 2, but that's old news, we don't care any more. Only when you see a new biggest gap, you report it. This reflects how the primes are getting less and less frequent, as the gaps become wider and wider.


EDIT: Most of the answers are brilliant and deserve more recognition. However, so far, a GolfScript entry with 48 characters is the shortest.

share|improve this question
1  
In your example 3 is the end of a pair, and the start of the next pair, while this is not the case for other numbers. What do you want? –  mmumboss Mar 12 at 12:20
    
Nevermind, I got it now. –  mmumboss Mar 12 at 12:45
    
You may want to rewrite your rule as "no builtin functions for prime testing, prime calculation or prime gaps". Otherwise an obvious solution would use a function that returns the n th prime, then increment n, run the function again and find the difference. –  ace Mar 12 at 13:25
2  
Aww. i love OEIS –  TheDoctor Mar 12 at 14:50
    
I have the same doubt as @mmumboss. Could you please xplain? –  Clyde Lobo Mar 12 at 15:04

27 Answers 27

up vote 3 down vote accepted

GolfScript 66 59 57 49 48

[2.0{:d{;\;.{).{(1$1$%}do(}do.2$-.d>!}do].p~.}do

Although I'm having trouble running it here http://golfscript.apphb.com/ (maybe that site doesn't like the infinite loop?) but it works fine when I run it on my computer with golfscript.rb. I'm pretty new to GolfScript so this can probably be golfed down even further. UPDATE: I don't think this can be golfed down much more without changing the algorithm somehow.

First few lines printed (If you do not like the "" being printed you can add ; at the beginning of the script, but that bumps it up to 49 chars) :

[2 3 1]
["" 3 5 2]
["" 7 11 4]
["" 23 29 6]
["" 89 97 8]
["" 113 127 14]
["" 523 541 18]
["" 887 907 20]
["" 1129 1151 22]
...

General human-readable idea of how this works (a few things slightly different since I'm not using a stack in this version) :

cur_prime = 2
next_prime = 2
gap = 0        

do {
    do {
        cur_prime = next_prime
        do {
            next_prime = next_prime + 1
            possible_factor = next_prime
            do {
                possible_factor = possible_factor - 1
            } while (next_prime % possible_factor > 0)
        } while (possible_factor != 1)
    } while (next_prime - cur_prime <= gap)

    gap = next_prime - cur_prime
    print [cur_prime next_prime gap]
} while (true)
share|improve this answer

Python, 121 110 109 108 104 103 characters

p,n,m=[2],3,0
while 1:
 if all(n%x for x in p):
  c=n-p[0]
  if m<c:m=c;print(p[0],n,c)
  p=[n]+p
 n+=1

First time I tried to answer here, I hope I did it right... not sure I even counted the characters right.

Hmmm, I could save another character on the print by downgrading to Python 2.x...

share|improve this answer
    
121 chars, make the title a heading with # , you seriously don't count the chars by hand do you? javascriptkit.com/script/script2/charcount.shtml –  user80551 Mar 12 at 12:43
    
No, I didn't count by hand :) But I've seen other Python answers to some questions flattened to one line in a way that reduced whitespace, and frankly I'm not sure whether a newline is counted as 1 or 2 characters... –  Tal Mar 12 at 12:49
1  
We count newlines as 1 character unless the question's rules explicitly state otherwise. Welcome to PPCG! –  Jonathan Van Matre Mar 12 at 12:50
3  
Welcome! Nice answer, and it also has some room for improvement. For example, if all(n%x>0for x in p): is a bit shorter. You can also save some characters by moving statements onto the same line (e.g. a=1;b=2;f()). –  grc Mar 12 at 12:57
1  
Latest change broke the code by not pushing [n] to the front like stated. –  orion Mar 12 at 19:04

JavaScript, 90 85 78 74 chars

Short Code (Google Closure Compiler - Advanced Optimizations; some manual edits; more edits by @MT0)

for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b)

Long Code

var lastPrime = 2,
    curNumber = lastPrime,
    maxDistance = 0,
    i;

// check all numbers
while( curNumber++ ) {

  // check for primes
  i = curNumber;
  while( curNumber % --i != 0 ) {}

  // if prime, then i should be equal to one here
  if( i == 1 ) {

    // calc distance
    i=curNumber-lastPrime;

    // new hit
    if( maxDistance < i ) {
      maxDistance = i;
      console.log( lastPrime, curNumber, maxDistance );
    }

    // remember prime
    lastPrime = curNumber;
  }
}

Output

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
...

Pretty inefficient test for primes, but that way it uses less characters.

First post here, so please excuse any mistakes.

share|improve this answer
    
78 Characters - for(a=b=2,c=0;b++;){for(d=b;b%--d;);1==d&&(c<b-a&&console.log(a,b,c=b-a),a=b)} –  MT0 Mar 18 at 21:39
    
@MT0 Thanks. Did not spot those. Edited. –  Sirko Mar 19 at 9:54
    
Even more inefficient but 74 characters - for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b) –  MT0 Mar 19 at 22:09

Mathematica, 114 108

Allows infinite output, although after a certain point in the sequence the fan spins up and you begin to suspect that your CPU is playing Freecell while doing its best to look busy.

p@x_:=NestWhile[#+1&,x+1,Divisors@#≠{1,#}&];m=0;q=1;While[1<2,If[p@q-q>m,Print@{q,p@q,p@q-q};m=p@q-q];q=p@q]

Output sample (These are the ones it picks up in the first ~30s):

{1,2,1}
{3,5,2}
{7,11,4}
{23,29,6}
{89,97,8}
{113,127,14}
{523,541,18}
{887,907,20}
{1129,1151,22}
{1327,1361,34}
{9551,9587,36}
{15683,15727,44}
{19609,19661,52}
{31397,31469,72}
{155921,156007,86}
{360653,360749,96}
{370261,370373,112}
{492113,492227,114}
{1349533,1349651,118}
{1357201,1357333,132}
{2010733,2010881,148}

Ungolfed code:

p@x_ := NestWhile[
   # + 1 &,
   x + 1,
   Divisors@# ≠ {1, #} &];
m = 0;
q = 1;
While[
 1 < 2,
 If[
  p@q - q > m,
  Print@{q, p@q, p@q - q}; m = p@q - q];
 q = p@q]
share|improve this answer
    
Does it recognize ? –  Riking Mar 13 at 1:39
    
Yes, it just doesn't export that way but it will parse it just fine when you paste code into the notebook. I've already scored it accordingly but I'll revise to simplify. –  Jonathan Van Matre Mar 13 at 1:44
    
how many characters if you do use mathematica's built-in Prime functions? –  Michael Stern Mar 20 at 16:32
    
76. Since the entire p@x_ definition is just a reimplementation of NextPrime, it can be replaced by p=NextPrime; –  Jonathan Van Matre Mar 20 at 16:47

Haskell - 122 116 114 112 110

q=[n|n<-[3..],all((>0).rem n)[2..n-1]]
d m((p,q):b)|q-p>m=print(p,q,q-p)>>d(q-p)b|q>p=d m b
main=d 0$zip(2:q)q

(Inefficient) prime list expression stolen from Will Ness.

-edit- I never knew x|y=z|w=q would be valid.

share|improve this answer

MATLAB 104 89

Just implemented the basic method by checking every possible division.

a=2;g=0;for n=3:inf;b=n*(sum(mod(n,1:n)<1)<3);h=b-a;if(h>g)g=h;[a,b,h]
end;a=max(a,b);end

Output:

  2     3     1
  3     5     2
  7    11     4
 23    29     6
 89    97     8
113   127    14
523   541    18
887   907    20
share|improve this answer
    
I'm on octave and this inf thing doesn't work (and print is deferred until the loop ends). Does matlab have lazy range evaluation? –  orion Mar 12 at 22:25
    
Matlab prints realtime, each iteration of the loop. When I start my program I get a warning that the maximum index is 2147483647, and then it starts. Alternatively I could replace inf with intmax, but that is three chars more. –  mmumboss Mar 13 at 6:48

Golfscript, 59 51 50 chars

Man each character is extremely difficult to lose:

0[2.{).,2>{\.@%!},{.2$-.4$>{].p~\[}{;\;}if..}or}do

Output:

[2 3 1]
[3 5 2]
[7 11 4]
[23 29 6]
[89 97 8]
[113 127 14]
...

Explanation:

The stack is set up so each iteration starts with the stack like this, the top being to the right. The [ indicates the current array marker, meaning when the interpreter encounters a ], everything on the stack from the mark to the top is put into an array.

g [ last | cur

g is the maximum gap so far. From the top down:

 command         | explanation
-----------------+----------------------------------------
 0[2.            | initialize vars g=0, last=2, cur=2
 {...}do         | loop forever...

Inside the loop:

 )               | cur += 1
 .,2>{\.@%!},    | put all divisors of cur into a list
 {...}or         | if the list is empty, cur is prime, so
                 | the block is executed. otherwise,
                 | 'do' consumes the stack, sees it is truthy,
                 | and loops again

How does it put all divisors into a list? Let's do it step by step

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | n
 .,              | make list of 0..n-1                          | n [0,1,...,n-1]
 2>              | take elements at index 2 and greater         | n [2,3,...,n-1]
 {...},          | take list off stack, then iterate through    |
                 | the list. on each iteration, put the current |
                 | element on the stack, execute the block, and |
                 | pop the top of the stack. if the top is      |
                 | true then keep the element, else drop it.    |
                 | when done, push list of all true elements    |
                 | So, for each element...                      | n x
   \.            |   Swap & dup                                 | x n n 
   @             |   Bring x around                             | n n x
   %             |   Modulo                                     | n (n%x)
   !             |   Boolean not. 0->1, else->0. Thus this is 1 |
                 |   if x divides n.                            | n (x divides n)
                 | So only the divisors of n are kept           | n [divisors of n]

What does it do if the divisors are empty?

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | g [ last | cur
  .              | dup                                          | g [ l | c | c
  2$             | copy 3rd down                                | g [ l | c | c | l
  -              | sub. This is the current gap, cur-last       | g [ l | c | c-l
  .              | dup                                          | g [ l | c | c-l | c-l
  4$             | copy 4th down                                | g [ l | c | c-l | c-l | g
  >              | is cur gap > max gap so far?                 | g [ l | c | c-l | c-l>g
  {#1}{#2}if..   | #1 if c-l > g, #2 otherwise, and do ".." in  | ... | g [ c | c | c
                 | either situation                             | 

Two paths: yes and no. If yes (note that if consumes the top value on the stack):

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. note that now the old `g` is  | XX [ l | c | g
                 | garbage and `c-l` is the new `g`.            |
 ]               | close the array                              | XX [l, c, g]
 .p              | duplicate it and print it, consuming the dup | XX [l, c, g]
 ~               | pump array back onto the stack. Note now the | XX | l | c | j
                 | array marker [ is gone.                      | 
 \               | swap.                                        | XX | l | g | c                         
 [               | mark the array                               | XX | l | g | c [
 .               | this is the part after the if. dups the top, | XX | l | g [ c | c
                 | but it does this in two steps, first popping | 
                 | c then putting two copies on top, so the     | 
                 | array marker moves                           | 
 .               | dup again                                    | XX | l | g [ c | c | c

If no:

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. In this case g is still the   | g [ l | c | c-l
                 | max gap so far                               | 
 ;\;             | dump top of stack, swap, and dump again      | g [ c
 ..              | the part after the if. dup twice             | g [ c | c | c

Note in either case, our stack is now in the form ... | g [ c | c | c.

Now the do pops the top value off the stack - always c - and loops if it is positive. Since c always increasing, this is always true, so we loop forever.

Once popped, the top of the stack is g [ c | c, meaning last has been updated to c, the array mark is in the same place, and g is still where we expect it.

These are the convoluted operations of GolfScript. I hope you enjoyed following along!

share|improve this answer
1  
Excellent elucidation! –  Jonathan Van Matre Mar 12 at 22:30

Ruby, 110

Only for Ruby 2.0 due to the lazymethod:

(2..1.0/0).lazy.select{|n|!(2...n).any?{|m|n%m==0}}.reduce([2,0]){|(l,t),c|d=c-l;p [l,c,d]if d>t;[c,d>t ?d:t]}

Output:

[2, 3, 1]
[3, 5, 2]
[7, 11, 4]
[23, 29, 6]
[89, 97, 8]
[113, 127, 14]
[523, 541, 18]
[887, 907, 20]
[1129, 1151, 22]
[1327, 1361, 34]
[9551, 9587, 36]
[15683, 15727, 44]
[19609, 19661, 52]
[31397, 31469, 72]
[155921, 156007, 86]
[360653, 360749, 96]
[370261, 370373, 112]
[492113, 492227, 114]
...
share|improve this answer

Perl, 105 bytes

$p=2;$d=0;L:for($i=2;++$i>2;){!($i%$_)&&next L for 2..$i-1;if($i-$p>$d){$d=$i-$p;print"$p $i $d\n"}$p=$i}

Ungolfed:

$p = 2;
$d = 0;
L: for ($i = 2; ++$i > 2; ){
    !($i % $_) && next L for 2..$i-1;
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}  

The algorithm is simple, $p remembers the previous prime number. Then $i goes from 3 up to, when the type $i "fails on me" or become negative because of overflow. $i is tested the crude way by checking all divisors from 2 to $i-1. A line is printed, if the current difference is larger than the previous printed difference $d.

With some more bytes the run-time can be improved:

$p = 2;
$d = 0;
L: for ($i=3; $i > 2; $i += 2){
    for ($j=3; $j <= sqrt($i); $j += 2){
        next L if !($i%$j)
    }
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}

The result starts with:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
155921 156007 86
360653 360749 96
370261 370373 112
492113 492227 114
1349533 1349651 118
1357201 1357333 132
2010733 2010881 148
4652353 4652507 154
17051707 17051887 180
20831323 20831533 210
47326693 47326913 220
...
share|improve this answer
1  
That's not correct, you need to find the series of increasing gaps. See for instance the Ruby or Matlab answer for the expected output. –  mmumboss Mar 12 at 13:39
1  
@mmumboss: Oh, I have overlooked this. Fixed now. –  Heiko Oberdiek Mar 12 at 14:05
    
Good for a language where all the variables require minimum 2 characters. –  orion Mar 12 at 14:13

Python, 93 91 chars

Naive prime checking (check if divisible by anything from 2 to n (less chars than to n/2)):

g=0;i=l=2
while 1:
 i+=1
 if all(i%x for x in range(2,i)):
    if i-l>g:g=i-l;print l,i,g
    l=i

Second level of indent is one tab character.

Output:

2 3 1
5 7 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
...
share|improve this answer
    
Nice, I forgot that range up to n only checks up to n-1 –  Claudiu Mar 12 at 18:56

76 chars, dogelang

Converted from my Python version:

g=0
i=l=2
while i+=1=>all$map(i%)(2..i)=>(i-l>g=>(g=i-l),print(l,i,g)),(l=i)

Output:

(2, 3, 1)
(3, 5, 2)
(7, 11, 4)
(23, 29, 6)
(89, 97, 8)
(113, 127, 14)
(523, 541, 18)
(887, 907, 20)
(1129, 1151, 22)
...
share|improve this answer
    
Should be selected as the winner! –  Sarge Borsch May 24 at 18:25

Bash and some Perl for prime regex (167 157 143 112 bytes)

n=2
c=2
while p=$c
do perl -e\(1x$[++n]')=~/^(11+?)\1+$/&&exit 1'&&c=$n
((c-p>g))&&g=$[c-p]&&echo $p $c $g
done

some output:

$./golfd.sh
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
share|improve this answer
    
Using regex's NP backtracking to completely circumvent any loops and control structures is pure perfection. However, test is protesting quite a lot, and it doesn't work for me. You could also use some let n++ and let f=c-p and replace test with [. Or possibly test in (()) where you don't need $ or spaces. –  orion Mar 12 at 21:11
    
test -n $d returned true for an empty string. test -n "$d" was fine but longer. However, man page says -n is optional, and it turns out test $d was ok. And therefore [ $d ] too. And g=0 had to be initialized. –  orion Mar 12 at 21:21
    
@orion, sorry for some reason it seemed to work once now it broke on my machine too, i reverted it to 167. I'll try to add some of your other suggestions –  Newbrict Mar 12 at 21:21
    
Your environment maybe had predefined variables. –  orion Mar 12 at 21:27
    
@orion for some reason your edit was rejected, can you re-edit? –  Newbrict Mar 12 at 21:35

Perl 95 90 bytes

for($n=$c=2;$p=$c;$c-$p>$g&&printf"$p $c %d\n",$g=$c-$p){$c=$n if(1x++$n)!~/^(11+?)\1+$/}

old Non golf version:

$n=$c=2;
while($p=$c){
    $c=$n if (1x++$n)!~/^(11+?)\1+$/;
    if ($c-$p>$g) {$g=$c-$p;print "$p $c $g\n"}
}

This is similar to my other submission, sans bash.

share|improve this answer
    
I'm not annoying, I just want to see how far can this go. Here: for($n=$c=2;$p=$c;$c-$p>$g&&printf"$p $c %d\n",$g=$c-$p){$c=$n if(1x++$n)!~/^(11+?)\1+$/} –  orion Mar 13 at 22:01
    
@orion that is some serious for loop abuse haha! –  Newbrict Mar 13 at 22:11

C (100)

My own contribution, no special algorithm, just golf:

i,g,r,p=2;main(){for(;r=p;p-r>g?printf("%d %d %d\n",r,p,g=p-r):0)for(i=0;i-p;)for(i=1,++p;p%++i;);}
share|improve this answer
    
" +10 characters if you only print the gaps without the primes." - if you remove printing of r and p you will have fewer characters and score the bonus :) –  CompuChip Mar 14 at 15:03
    
Completness is pretty :) –  orion Mar 14 at 16:21

Haskell, 134C

Golfed:

c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1
p=filter c[1..]
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)
main=g 0 p

Ungolfed:

-- c function checks if n is a prime number
c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1

-- p is an infinite list of primes
p=filter c[1..]

-- g function prints a list of primes and differences.
--   l is the maximum difference seen so far
--   (m:n:o) is the list of unprocessed primes
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)

-- main starts the ball rolling with a default max-seen value of 0
main=g 0 p
share|improve this answer
    
Love that lazy evaluation! –  Jonathan Van Matre Mar 16 at 13:13

C: 493 302 272 246

int e(int j){for(int i=2;i<j;i++)if(j%i<1)return 0;return 1;}void f(int a,int b,int c){if(e(a)&e(b))if(c<b-a){printf("%d %d %d\n",a,b,b-a);f(a+1,b+1,b-a);}else f(a+1,b+1,c);if(e(b))f(a+1,b,c);if(e(a))f(a,b+1,c);f(a+1,b+1,c);}int main(){f(2,3,0);}

I used recursion not the usual loop of for or while.

int isPrime(int num){
    for( int i=2; i<num; i++ )
        if(num%i < 0) return 0;
    return 1;
}
void fun(int n1, int n2, int gap){
   if( isPrime(n1) & isPrime(n2) ){
        if( gap < n2-n1 ){
           printf("%d %d %d\n", n1, n2, n2-n1);
           fun(n1+1, n2+1, n2-n1);
        }else{
           fun(n1+1, n2+1, gap);
        }
   }
   if( isPrime(n2) ){
       fun(n1+1, n2, gap);
   }
   if( isPrime(n1) ){
       fun(n1, n2+1, gap);
   }
   fun(n1+1, n2+1, gap);
}

int main(){
   fun(2,3,0);
}

Output:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
share|improve this answer
    
This doesn't work. true/false are not defined, but even if we fix that, it's reporting wrong gaps. For instance, there are A LOT of primes between 25219 and 43237. Your recursion is leaking at the top, because you are not testing isPrime(n2), you are letting primes between n1 and n2. And this can't really be fixed, because you can't increase n2 without meeting primes. –  orion Mar 13 at 7:56
    
You are right! It is wrong! My thinking was wrong from the beginning. –  Loukas Mar 13 at 8:10
1  
Now it is better.. :) –  Loukas Mar 13 at 8:50
    
+1 Now that it's fixed I like it - it's nicely unusual (although not efficient). You could golf it down a lot. Skip return in main. Skip the last else. Replace && -> & and num%i==0 with num%i<1. And by the ancient c standards (there will be warnings), you don't need to specify return values for void and int functions (their arguments also default to int). –  orion Mar 13 at 15:27
    
Thanks for the update! –  Loukas Mar 14 at 7:30

Oracle SQL, 216 202 196 172 + 10 = 182

Just noticed this in the question:

Lowest character count wins. +10 characters if you only print the gaps without the primes.

As this is SQL and the keywords are so long it's actually better to take the penalty, giving the following. It's the same idea as the original.

with c as(select level+1n from dual connect by level<1e124)select lead(n)over(order by n) from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0))

which prettifies to:

with c as ( 
 select level + 1 n 
   from dual 
connect by level < 1e124
        )
select lead(n) over ( order by n ) 
  from ( select *
           from c a 
          where not exists( select * 
                              from c 
                             where n < a.n 
                               and mod(a.n, n) = 0
                                   )
                )

Old answer (196)

with c as(select level+1n from dual connect by level<1e124)select n,p,p-n from(select n,lead(n)over(order by n)p from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0)))

and in a readable format:

with c as ( 
 select level + 1 n 
   from dual 
connect by level < 1e124
        )
select n, p, p-n 
  from ( select n, lead(n) over ( order by n ) p 
           from ( select * 
                    from c a 
                   where not exists (
                                select * 
                                  from c
                                 where n < a.n 
                                   and mod(a.n, n) = 0
                                       )
                         )
                )

This creates a number generator in c, the innermost sub-select creates the primes numbers using a Sieve of Eratosthenes, the outer works out the previous prime and finally the last select subtract one from the other.

This won't return anything because it's performing 1 x 10 124 recursive queries... So, if you want it to work lower this number to something sensible.

share|improve this answer
    
When it comes to a challenge like this one, I think of SQL as not so much Turing-complete, but Turing-obstinate. –  Jonathan Van Matre Mar 14 at 13:23
    
But it is Turning-complete @Jonathan, though getting it there is sometimes "interesting" :-)? –  Ben Mar 14 at 13:34
    
Knowing it is Turing-complete, I was aiming to jest. Missed the mark, apparently. :) Anyway, there are several T-SQL answers in my profile...bring your Oracle and let's have a duel! –  Jonathan Van Matre Mar 14 at 14:10

D - 153 + 10 = 163

I'm willingly taking the +10 penalty here, because the char count is still lower than it would have been if I had printed the primes as well.

Golfed:

import std.stdio;bool p(int l){int n;foreach(i;1..l+1)n+=l%i==0?1:0;return n==2;}void main(){int g;foreach(l;0..int.max)if(l.p){if(g>0)(l-g).write;g=l;}}

Readable version:

import std.stdio;

bool prime( int number )
{
    int divisors;

    foreach( i; 1 .. number + 1 )
        divisors += number % i == 0 ? 1 : 0;

    return divisors == 2;
}

void main()
{
    int lastPrime;

    foreach( number; 0 .. int.max )
        if( number.prime )
        {
            if( lastPrime > 0 )
                ( number - lastPrime ).write;

            lastPrime = number;
        }
}
share|improve this answer

JAVASCRIPT 174 char

var p=[2],l=2,g=0;
for(var n=3;n>0;n+=2){
  var o=0;
  for(var t=0;t<p.length;++t){
    if(n/p[t] == parseInt(n/p[t])){
      o=1;
    }
  }
  if(o==0){
    p.push(n);
    if(n-l>g){
      g=n-l;
      console.log(l,n,g);
    }
    l=n;
  }
}

short version:

var p=[2],l=2,g=0;for(var n=3;n>0;n+=2){var o=0;for(var t=0;t<p.length;++t){if(n/p[t] == parseInt(n/p[t])){o=1;}}if(o==0){p.push(n);if(n-l>g){g=n-l;console.log(l,n,g);}l=n;}}
share|improve this answer

Javascript 138

for(var a=2,b=0,c=0;a++;){var d;a:{for(var e=a,f=2;f<e;f++)if(0==e%f){d=!1;break a}d=!0}d&&(0!=b&&a-b>c&&(c=a-b,console.log(b,a,c)),b=a)}

Copy this code to your browser console. It will for like forever as the max number is something around 1.79*10^308.

Ungolfed:

var number = 2;
var lastPrime = 0;
var gap = 0;

while(number++)
{
    if (isPrime(number)) {
        if (lastPrime != 0) {            
            if (number - lastPrime > gap)
            {
                gap = number - lastPrime;
                console.log(lastPrime, number, gap);
            }
        }

        lastPrime = number;
    }
}

function isPrime(n){
    for (var i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
share|improve this answer

C# 162 161 chars

151 chars + 10 penalty chars = 161 chars

Short version:

using System;class P{static void Main(){int p=2,g=0;for(int i=3;;i++){for(int j=2;j<i;j++)if(i%j==0)goto e;if(i-p>g)Console.WriteLine(g=i-p);p=i;e:;}}}

Long version:

using System;

class PrimeGaps
{
    private static void Main()
    {
        int lastPrime = 2;
        int largestGap = 0;

        for (int i = 3; true; i++)
        {
            // Prime test
            for (int j = 2; j < i; j++)
                if (i%j == 0)
                    goto nextI; // Skip to next iteration of i

            // Largest gap check
            if (i - lastPrime > largestGap)
            {
                largestGap = i - lastPrime;
                Console.WriteLine(largestGap);
            }

            // Remember last prime
            lastPrime = i;

            nextI:
                ; // Do nothing
        }
    }
}

It was actually better to take 10 chars penalty, since it's shorter writing g (11 chars with penalty) than p+" "+i+" "+g (13 chars without penalty).

share|improve this answer

Ruby 90 86 84 83 chars

r,i,g=2,2,0;while i+=1 do(2...i).all?{|j|i%j>0}&&((i-r<=g||p([r,i,g=i-r]))&&r=i)end

Some boolean short circuits, abuse of expression evaluation, etc.

share|improve this answer

C 248

Code compares consecutive prime numbers a, b and then checks if gaps are larger than g then finds next pair of primes.

#include <cstdio>
void f(int* a, int* b){*a =*b;int t=1;while (*b += 2){t=1;for(int i=3;i<*b;i+=2){if(*b%i==0){t=0; break;}}if(t)break;}}
int main(){int a=2,b=3,g=0;do{(b-a>g)?printf("%d %d %d\n",a,b,(g=b-a)): f(&a,&b);} while(b>=0);return 0;}
share|improve this answer

Haskell, 154 144 137 123

The primes p are generated using the sieve of erasthotenes #, and then filtered and printed using %.

p=2:3#1
n#m|all((>0).mod n)$take m p=n:(n+1)#(m+1)|1<2=(n+1)#m
(l:u@(o:_))%k|o-l>k=print(l,o,o-l)>>u%(o-l)|1<2=u%k
main=p%0

The output looks like

(2,3,1)
(3,5,2)
(7,11,4)
(23,29,6)
(89,97,8)

which I hope is okay.

share|improve this answer

Game Maker Language, 85

Assuming all uninitialized variables as 0 (this is the default with some versions of Game Maker).

a=2b=2for(d=2;b++;1)for(c<b-a;b mod --d;1)d<3&&(c=b-a&&show_message_ext("",a,b,c)a=b)
share|improve this answer

Game Maker Language, 74 + 55 = 129

Assuming all uninitialized variables as 0 (this is the default with some versions of Game Maker).

n=2while(n++){if p(n){if l{if n-l>g{g=n-l;show_message_ext("",l,n,g)}}l=n}

Script p is below:

r=1a=argument0for(i=2i<a;i++){if a mod i=0r=0}return r}
share|improve this answer

Perl 153

Short code:

$i=$a=2;while($a=$i++){if(p($i)){if($m<$m2=$i-$a){$m=$m2;print"$a $i $m$/"}}}sub p{$d=2;$s=sqrt$_[0];while(){return 0if!($_[0]%$d);return 1if$d>$s;$d++}}

easy to Read:

$i=$a=2;
while($a=$i++){
  if(p($i)){
    if($m<$m2=$i-$a){
      $m=$m2;
      print"$a $i $m$/"
    }
  }
}
sub p {
  $d=2;
  $s=sqrt$_[0];
  while(){
    return 0if!($_[0]%$d);
    return 1if$d>$s;
    $d++;
  }
}
share|improve this answer
    
This outputs all gaps, not just the biggest so far. –  orion Mar 12 at 13:37

Your Answer

 
discard

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.