Following the fine tradition of questions such as Find the largest prime whose length, sum and product is prime , this is a variant on a largest prime challenge.
Your code should not take any input.
We say a prime
p-1 has exactly
2 distinct prime factors.
Your code should output the absolute difference between consecutive good primes
p so that
|q-p| is as large as possible and
q is the smallest good prime larger than
p. You may output any number of good pairs and your last output will be taken as the score.
The sequence of the first 55 good primes is https://oeis.org/A067466 .
Your score is simply
|q-p| for the pair of good primes you output.
Languages and libraries
You can use any language or library you like (that wasn't designed for this challenge) except for any library functions for primality testing or factoring integers. However, for the purposes of scoring I will run your code on my machine so please provide clear instructions for how to run it on Ubuntu.
My Machine The timings will be run on my machine. This is a standard Ubuntu install on an 8GB AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.
- I will kill your code after 2 minutes unless it starts to run out of memory before that. It should therefore make sure to output something before the cut off.
- You may not use any external source of primes.
- You may use probabilistic prime testing methods although I am told by Mego that with good tables, Miller-Rabin can test up to 341,550,071,728,321 (or even higher) deterministically. See also http://miller-rabin.appspot.com/ .
Best entries that check all integers from 1
- 756 by cat in Go
- 756 by El'endia Starman in Python
- 1932 by Adnan in C# (using mono 3.2.8)
- 2640 by yeti in Python (using pypy 4.01)
- 2754 by Reto Koradi in C++
- 3486 by Peter Taylor in Java
- 3900 by primo in RPython (using pypy 4.01)
- 4176 by The Coder in Java
Best entries that may skip a large number of integers to find a large gap
- 14226 by Reto Koradi in C++
- 22596 by primo in RPython (using pypy 4.01). Record reached after 5 seconds!