0
$\begingroup$

Counting up from zero, if you find a prime number, is there a certain intervall you can skip knowing for sure that sequent prime number will not be skipped?

For reference, I am writing a program which searchs for prime numbers by checking every number up from 2. The problem is that once the number is big enough it takes very much time to find the next number. For example, if the program detects a 10-digit prime number, can I skip a certain intervall knowing that the next one won't be left out?

$\endgroup$
10
  • 3
    $\begingroup$ Twin primes will pose a problem for this. $\endgroup$
    – Randall
    Nov 27 '20 at 14:18
  • 2
    $\begingroup$ You can skip every even number. $\endgroup$
    – user838035
    Nov 27 '20 at 14:21
  • 2
    $\begingroup$ Either you need more efficient primality tests (there are much better tests than the cumbersome and very slow trial division) , or (even better) , you apply sieving algorithms , but in this case you might have to partition the intervals because of memeory issues) $\endgroup$
    – Peter
    Nov 27 '20 at 14:24
  • 4
    $\begingroup$ It sounds like you're searching for primes by doing trial division on every number. That's not very efficient. Take a look at the sieve of Eratosthenes. Or wheel sieves. If you want to search for primes without specifying an upper limit (and without storing all primes found so far), there are ways to do that too, eg the segmented sieve. $\endgroup$
    – PM 2Ring
    Nov 27 '20 at 14:26
  • 1
    $\begingroup$ @hardmath This is not quite true. The best known unconditional result is that prime gaps with difference $246$ or less occur infinite many often. For no concrete gap it is known whether it occurs infinite many often. The version with difference $6$ needs a conjecture that is not yet proven. Additionally, I do not see how this result would help the author with his program. $\endgroup$
    – Peter
    Nov 27 '20 at 14:27
6
$\begingroup$

No, but you can do something similar. The first 3 primes are $2, 3, 5$ and $2\cdot 3\cdot 5 = 30$. If a number is greater than $30$ and prime then it must be congruent to $1, 7, 11, 13, 17, 19, 23,$ or $29$ modulo $30$.

So for every block of 30 numbers, you need only check 8 of them.

You can expand this method by using more than the first 3 primes.

$\endgroup$
3
  • 1
    $\begingroup$ (+1) because this solution also considers the needed memory. $\endgroup$
    – Peter
    Nov 27 '20 at 14:55
  • 1
    $\begingroup$ For anybody interested, this is basically an example of wheel factorization. $\endgroup$ Nov 27 '20 at 17:45
  • $\begingroup$ This can also be used to create a compact table of primes, since it lets you represent each block of 30 numbers by a single byte. $\endgroup$
    – PM 2Ring
    Nov 28 '20 at 1:54
0
$\begingroup$

Chebyshev said it, I'll say it again:
There's always a prime between $n$ and $2n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.