Earliest difference between prime gaps: Difference between revisions
Content added Content deleted
m (typo) |
(Added Java solution) |
||
Line 69: | Line 69: | ||
Note: the earliest value found for each order of magnitude may not be unique, in fact, ''is'' not unique; also, with the gaps in ascending order, the minimal starting values are not strictly ascending. |
Note: the earliest value found for each order of magnitude may not be unique, in fact, ''is'' not unique; also, with the gaps in ascending order, the minimal starting values are not strictly ascending. |
||
=={{header|Java}}== |
|||
Uses the PrimeGenerator class from [[Extensible prime generator#Java]]. |
|||
<lang java>import java.util.HashMap; |
|||
import java.util.Map; |
|||
public class PrimeGaps { |
|||
private Map<Integer, Integer> gapStarts = new HashMap<>(); |
|||
int lastPrime; |
|||
PrimeGenerator primeGenerator = new PrimeGenerator(1000, 500000); |
|||
public static void main(String[] args) { |
|||
final int limit = 100000000; |
|||
PrimeGaps pg = new PrimeGaps(); |
|||
for (int pm = 10, gap1 = 2;;) { |
|||
int start1 = pg.findGapStart(gap1); |
|||
int gap2 = gap1 + 2; |
|||
int start2 = pg.findGapStart(gap2); |
|||
int diff = start2 > start1 ? start2 - start1 : start1 - start2; |
|||
if (diff > pm) { |
|||
System.out.printf( |
|||
"Earliest difference > %,d between adjacent prime gap starting primes:\n" |
|||
+ "Gap %,d starts at %,d, gap %,d starts at %,d, difference is %,d.\n\n", |
|||
pm, gap1, start1, gap2, start2, diff); |
|||
if (pm == limit) |
|||
break; |
|||
pm *= 10; |
|||
} else { |
|||
gap1 = gap2; |
|||
} |
|||
} |
|||
} |
|||
private int findGapStart(int gap) { |
|||
Integer start = gapStarts.get(gap); |
|||
if (start != null) |
|||
return start; |
|||
for (;;) { |
|||
int prev = lastPrime; |
|||
lastPrime = primeGenerator.nextPrime(); |
|||
int diff = lastPrime - prev; |
|||
gapStarts.putIfAbsent(diff, prev); |
|||
if (diff == gap) |
|||
return prev; |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Earliest difference > 10 between adjacent prime gap starting primes: |
|||
Gap 4 starts at 7, gap 6 starts at 23, difference is 16. |
|||
Earliest difference > 100 between adjacent prime gap starting primes: |
|||
Gap 14 starts at 113, gap 16 starts at 1,831, difference is 1,718. |
|||
Earliest difference > 1,000 between adjacent prime gap starting primes: |
|||
Gap 14 starts at 113, gap 16 starts at 1,831, difference is 1,718. |
|||
Earliest difference > 10,000 between adjacent prime gap starting primes: |
|||
Gap 36 starts at 9,551, gap 38 starts at 30,593, difference is 21,042. |
|||
Earliest difference > 100,000 between adjacent prime gap starting primes: |
|||
Gap 70 starts at 173,359, gap 72 starts at 31,397, difference is 141,962. |
|||
Earliest difference > 1,000,000 between adjacent prime gap starting primes: |
|||
Gap 100 starts at 396,733, gap 102 starts at 1,444,309, difference is 1,047,576. |
|||
Earliest difference > 10,000,000 between adjacent prime gap starting primes: |
|||
Gap 148 starts at 2,010,733, gap 150 starts at 13,626,257, difference is 11,615,524. |
|||
Earliest difference > 100,000,000 between adjacent prime gap starting primes: |
|||
Gap 198 starts at 46,006,769, gap 200 starts at 378,043,979, difference is 332,037,210. |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |