Largest difference between adjacent primes
- 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 should be specified to allow a larger heap size.
As with the Wren, Phix, etc. samples, shows the gaps at a few other places.
<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
<lang c>#include<stdio.h>
- 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.
Factor
See Largest difference between adjacent primes/Factor for a detailed explanation because why not?
<lang factor>USING: arrays formatting kernel lists lists.lazy math math.order math.primes.lists sequences ;
lprimes dup cdr lzip [ first2 2dup swap - -rot 3array ] lmap-lazy [ second 1e6 < ] lwhile { 0 } [ max ] foldl
"Largest difference in adjacent primes under a million: %d between %d and %d.\n" vprintf</lang>
- Output:
Largest difference in adjacent primes under a million: 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>
Julia
<lang julia>using Primes
function maxprimeinterval(nmax)
pri = primes(nmax)
diffs = [pri[i] - pri[i - 1] for i in 2:length(pri)]
diff, idx = findmax(diffs)
println("The maximum prime interval in primes up to $nmax is $diff: for example at [$(pri[idx]), $(pri[idx + 1])].")
end
foreach(n -> maxprimeinterval(10^n), 1:10)
</lang>
- Output:
The maximum prime interval in primes up to 10 is 2: for example at [3, 5]. The maximum prime interval in primes up to 100 is 8: for example at [89, 97]. The maximum prime interval in primes up to 1000 is 20: for example at [887, 907]. The maximum prime interval in primes up to 10000 is 36: for example at [9551, 9587]. The maximum prime interval in primes up to 100000 is 72: for example at [31397, 31469]. The maximum prime interval in primes up to 1000000 is 114: for example at [492113, 492227]. The maximum prime interval in primes up to 10000000 is 154: for example at [4652353, 4652507]. The maximum prime interval in primes up to 100000000 is 220: for example at [47326693, 47326913]. The maximum prime interval in primes up to 1000000000 is 282: for example at [436273009, 436273291]. The maximum prime interval in primes up to 10000000000 is 354: for example at [4302407359, 4302407713].
Perl
<lang perl>use strict; use warnings; use Primesieve qw(generate_primes);
for my $n (2..8) {
my @primes = generate_primes (1, 10**$n);
my($max,$p,$diff) = 0;
map { ($diff = $primes[$_] - $primes[$_-1]) > $max and ($max,$p) = ($diff,$_-1) } 1..$#primes;
printf "Largest prime gap up to %d: %d - between %d and %d.\n", 10**$n, $max, @primes[$p,$p+1];
}</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.
Phix
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.
Python
<lang python> print("working...") limit = 1000000 res1 = 0 res2 = 0 maxOld = 0 newDiff = 0 oldDiff = 0
def isPrime(n):
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
for n in range(limit):
newDiff = n - maxOld
if isprime(n):
if (newDiff > oldDiff):
res1 = n
res2 = maxOld
oldDiff = newDiff
maxOld = n
diff = res1 - res2 print(res1) print(res2) print("Largest difference is = ",end="") print(diff) print("done...") </lang>
- Output:
492227 492113 Largest difference is = 114
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
<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