Largest difference between adjacent primes

Largest difference between adjacent primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Find and show on this page the largest difference between adjacent primes under 1,000,000.

ALGOL 68

Note, to run this with Algol 68G, the command line option --heap 256M whould be specified on the command line to allow a larger heap size.
As with the Wren, Phix, etc. samples, shows the gaps for at a few other places.

Library: ALGOL 68-primes

<lang algol68>BEGIN # find the largest gap between adjacent primes up to 10 000 000 #

   PR read "primes.incl.a68" PR
   []BOOL prime = PRIMESIEVE 10 000 000; # sieve the primes to 10 000 000 #
   # find the largest gap between primes #
   INT max gap     :=  0; # gap between 2 and 3 #
   INT max prime   :=  0; # the prime with the maximum gap #
   INT max prev    :=  0; # the prime before the maximum gap #
   INT prev prime  :=  2; # the previous prime #
   INT power of 10 := 10; # next number to print the gap for #
   FOR i FROM 3 BY 2 TO UPB prime DO
       IF prime[ i ] THEN
           # have a prime #
           INT gap = i - prev prime;
           IF gap > max gap THEN
               # have a bigger gap than before #
               max prime := i;
               max prev  := prev prime;
               max gap   := gap
           FI;
           prev prime    := i
       FI;
       IF i = power of 10 - 1 THEN
           # have reached the next power of 10 - report the max gap so far #
           print( ( "Largest gap between primes up to ", whole( power of 10, -9 )
                  , ": ", whole( max gap, -9 ), " between "
                  , whole( max prev, 0 ), " and ", whole( max prime, 0 )
                  , newline
                  )
                );
           power of 10 *:= 10
       FI
   OD

END</lang>

Output:

Largest gap between primes up to        10:         2 between 3 and 5
Largest gap between primes up to       100:         8 between 89 and 97
Largest gap between primes up to      1000:        20 between 887 and 907
Largest gap between primes up to     10000:        36 between 9551 and 9587
Largest gap between primes up to    100000:        72 between 31397 and 31469
Largest gap between primes up to   1000000:       114 between 492113 and 492227
Largest gap between primes up to  10000000:       154 between 4652353 and 4652507

C

Translation of: FreeBASIC

<lang c>#include<stdio.h>

1. include<stdlib.h>

int isprime( int p ) {

   int i;
   if(p==2) return 1;
   if(!(p%2)) return 0;
   for(i=3; i*i<=p; i+=2) {
      if(!(p%i)) return 0;
   }
   return 1;

}

int nextprime( int p ) {

   int i=0;
   if(p==0) return 2;
   if(p<3) return p+1;
   while(!isprime(++i + p));
   return i+p;

}

int main(void) {

   int i=3, j=5, champ=3, champj=5, record=2;
   for(i=3;j<=1000000;i=j) {
       j=nextprime(i);
       if(j-i>record) {
           champ=i;
           champj=j;
           record = j-i;
       }
   }
   printf( "The largest difference was %d, between %d and %d.\n", record, champ, champj );
   return 0;

}</lang>

Output:

The largest difference was 114, between 492113 and 492227.

FreeBASIC

<lang freebasic>#include "isprime.bas"

function nextprime( n as uinteger ) as uinteger

   'finds the next prime after n
   if n = 0 then return 2
   if n < 3 then return n + 1
   dim as integer q = n + 2
   while not isprime(q)
       q+=2
   wend
   return q

end function

dim as uinteger i = 5, j, champ=3, champj=5, record=2 while i<1000000

   j = nextprime(i)
   if j-i > record then
       champ  = i
       champj = j
       record = j - i
   end if
   i = j

wend

print using "The largest difference was ####, between ####### and #######";record;champ;champj</lang>

Output:

The largest difference was   114 between  492113 and  492227

GW-BASIC

<lang gwbasic>10 R=2 : P=3 : P2=0 20 GOSUB 190 30 IF P2>1000000! THEN GOTO 70 40 IF P2-P > R THEN GOSUB 270 50 P=P2 60 GOTO 20 70 PRINT "The biggest difference was ";R;", between ";C1;" and ";C2 80 END 90 REM tests if a number is prime 100 Q=0 110 IF P = 2 THEN Q = 1:RETURN 120 IF P=3 THEN Q=1:RETURN 130 I=1 140 I=I+1 150 IF INT(P/I)*I = P THEN RETURN 160 IF I*I<=P THEN GOTO 140 170 Q = 1 180 RETURN 190 REM finds the next prime after P, result in P2 200 IF P = 0 THEN P2 = 2: RETURN 210 IF P<3 THEN P2 = P + 1: RETURN 220 T = P 230 P = P + 1 240 GOSUB 90 250 IF Q = 1 THEN P2 = P: P = T: RETURN 260 GOTO 230 270 C1=P 280 C2 = P2 290 R = P2 - P 300 RETURN</lang>

Phix

Translation of: Wren

with javascript_semantics
atom t0 = time()
constant limit = iff(platform()=JS?1e8:1e9) - 1
sequence primes = get_primes_le(limit)
integer maxI = 0,
        maxDiff = 0
atom nextStop = 10
printf(1,"The largest differences between adjacent primes under the following limits is:\n")
for i=2 to length(primes) do
    integer diff = primes[i] - primes[i-1]
    if diff>maxDiff then
        maxDiff = diff
        maxI = i
    end if
    if i==length(primes) or primes[i+1]>nextStop then
        printf(1,"Under %,d: %,d - %,d = %,d\n", {nextStop, primes[maxI], primes[maxI-1], maxDiff})
        nextStop *= 10
    end if
end for
?elapsed(time()-t0)

Output:

The largest differences between adjacent primes under the following limits is:
Under 10: 5 - 3 = 2
Under 100: 97 - 89 = 8
Under 1,000: 907 - 887 = 20
Under 10,000: 9,587 - 9,551 = 36
Under 100,000: 31,469 - 31,397 = 72
Under 1,000,000: 492,227 - 492,113 = 114
Under 10,000,000: 4,652,507 - 4,652,353 = 154
Under 100,000,000: 47,326,913 - 47,326,693 = 220
Under 1,000,000,000: 436,273,291 - 436,273,009 = 282
"12.7s"

Almost all the time is spent constructing the list of primes. It is about 4 times slower under pwa/p2js so limited to 1e8 when running in a browser to keep the time below 5s instead of over 50s.

Raku

Built-ins

<lang perl6>for 2..8 -> $n {

   printf "Largest prime gap up to {10 ** $n}: %d - between %d and %d.\n", .[0], |.[1]
     given max (^10**$n).grep(&is-prime).rotor(2=>-1).map({.[1]-.[0],$_})

}</lang>

Output:

Largest prime gap up to 100: 8 - between 89 and 97.
Largest prime gap up to 1000: 20 - between 887 and 907.
Largest prime gap up to 10000: 36 - between 9551 and 9587.
Largest prime gap up to 100000: 72 - between 31397 and 31469.
Largest prime gap up to 1000000: 114 - between 492113 and 492227.
Largest prime gap up to 10000000: 154 - between 4652353 and 4652507.
Largest prime gap up to 100000000: 220 - between 47326693 and 47326913.

Or, significantly faster using a

Module

<lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;

for 2..8 -> $n {

   printf "Largest prime gap up to {10 ** $n}: %d - between %d and %d.\n", .[0], |.[1]
     given max $sieve.primes(10 ** $n).rotor(2=>-1).map({.[1]-.[0],$_})

}</lang> Same output

Ring

<lang ring> load "stdlib.ring" see "working..." + nl limit = 1000000 Primes = [] maxOld = 0 newDiff = 0 oldDiff = 0

for n = 1 to limit

   newDiff = n - maxOld
   if isprime(n) 
      if newDiff > oldDiff
         add(Primes,[n,maxOld])
         oldDiff = newDiff
      ok
      maxOld = n
   ok

next

len = len(Primes) diff = Primes[len][1] - Primes[len][2] see Primes[len(Primes)] see nl + "Largest difference is = " + diff + nl see "done..." + nl </lang>

Output:

working...
492227
492113
Largest difference is = 114
done...

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "./math" for Int import "/fmt" for Fmt

var limit = 1e9 - 1 var primes = Int.primeSieve(limit) var maxI = 0 var maxDiff = 0 var nextStop = 10 System.print("The largest differences between adjacent primes under the following limits is:") for (i in 1...primes.count) {

   var diff = primes[i] - primes[i-1]
   if (diff > maxDiff) {
       maxDiff = diff
       maxI = i
   }
   if (i == primes.count - 1 || primes[i+1] > nextStop)  {
       Fmt.print("Under $,d: $,d - $,d = $,d", nextStop, primes[maxI], primes[maxI-1], maxDiff)
       nextStop = nextStop * 10
   }

}</lang>

Output:

The largest differences between adjacent primes under the following limits is:
Under 10: 5 - 3 = 2
Under 100: 97 - 89 = 8
Under 1,000: 907 - 887 = 20
Under 10,000: 9,587 - 9,551 = 36
Under 100,000: 31,469 - 31,397 = 72
Under 1,000,000: 492,227 - 492,113 = 114
Under 10,000,000: 4,652,507 - 4,652,353 = 154
Under 100,000,000: 47,326,913 - 47,326,693 = 220
Under 1,000,000,000: 436,273,291 - 436,273,009 = 282

XPL0

<lang XPL0>def Size = 1_000_000_000/2; \sieve for odd numbers int Prime, I, K; char Flags; int Limit, TenToThe, Max, Gap, I0, Prime0, Prime1; [Flags:= MAlloc(Size+1); \(heap only provides 64 MB) for I:= 0 to Size do \set flags all true

   Flags(I):= true;

for I:= 0 to Size do

   if Flags(I) then                    \found a prime
       [Prime:= I+I+3;
       K:= I+Prime;                    \first multiple to strike off
       while K <= Size do              \strike off all multiples
           [Flags(K):= false;
           K:= K+Prime;
           ];
       ];

Text(0, "Largest difference between adjacent primes under: "); Limit:= 10; for TenToThe:= 1 to 9 do

   [Max:= 0;  I0:= 0;
   for I:= 0 to Limit/2-3 do
       [if Flags(I) then               \odd prime
           [Gap:= I - I0;
           if Gap > Max then
               [Max:= Gap;
               Prime0:= I0*2 + 3;
               Prime1:= I *2 + 3;
               ];
           I0:= I;
           ];
       ];
   IntOut(0, Limit);  Text(0, " is ");
   IntOut(0, Prime1); Text(0, " - ");
   IntOut(0, Prime0); Text(0, " = ");
   IntOut(0, Max*2);  CrLf(0);
   Limit:= Limit*10;
   ];

]</lang>

Output:

Largest difference between adjacent primes under:
10 is 5 - 3 = 2
100 is 97 - 89 = 8
1000 is 907 - 887 = 20
10000 is 9587 - 9551 = 36
100000 is 31469 - 31397 = 72
1000000 is 492227 - 492113 = 114
10000000 is 4652507 - 4652353 = 154
100000000 is 47326913 - 47326693 = 220
1000000000 is 436273291 - 436273009 = 282