1

I was going through the basics of trial division primality test, and hence, implementing it in code. The performance of the algorithm can be increased using many tricks like:

1) running the trial division only up to square-root(n)

2) trading memory for time by creating a sieve up to square-root(n), and then running the trial division only on the primes in the created sieve

But nowhere did I find the idea of returning the result as composite if the value of n%6 (n mod 6) if found out to be 1 or 5 (using the 6k +/- 1 rule). Will using this rule in our prime number determination test not improve its performance? If yes, why hasn't it been mentioned anywhere? If no, why is it so?

Thanks.

Tanmay Garg
  • 801
  • 11
  • 20
  • sorry not an answer but hint instead What about using periodic/cyclic sieves? see [Prime numbers by Eratosthenes quicker sequential than concurrently?](http://stackoverflow.com/a/22477240/2521214) – Spektre Jun 26 '16 at 15:37

4 Answers4

3

It seems you fall into the category above the beginner level (people who would never come up with the idea) and below people looking for extreme performance. So the idea is a bit difficult to explain to the beginners, and seems trivial to the very advanced ones.

It reduces the running time by one third, or lets you test 50% more numbers in the same time. You can save a bit more by doing fewer tests that the divisor isn't too large: Let's say you test a number around a billion. You have a loop, with a divisor d = 6k-1, and you want to test d and d+2 = 6k+1. So you only test that d^2 ≤ p, you don't test that (d+2)^2 ≤ p. Worst case, you test one divisor more than you needed. Best case, you save a few thousand tests that (d+2)^2 ≤ p.

You can save slightly more by observing that the only possible primes ≥ 30 are 30k + 1, 7, 11, 13, 17, 19, 23, 29, avoiding 30k + 5 and 30k + 25.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
  • His actual idea is to first test `n%6` as a preliminary filter before launching into trial division. That idea isn't very helpful, but this answer shows how it can be modified to be helpful. – John Coleman Jun 26 '16 at 13:36
  • I like the part where you can ignore the `(d+2)^2 ≤ p` test, and incur a worst case loss of just another divisor. Really thoughtful, thanks! – Tanmay Garg Jun 26 '16 at 13:46
1

Your idea of testing n % 6 is completely equivalent to testing n % 2 and n % 3 -- hence if you do the latter as part of your ordinary trial division then doing the former is redundant.

A closely related idea which does pay off is to (after considering 2 and 3) only look at trial divisors of the form 6k+1, 6k-1, as @gnasher729 explains in their excellent answer.

John Coleman
  • 51,337
  • 7
  • 54
  • 119
1

The way this trick works: Make the product of M of a bunch of small primes. Then, when testing a number N, you can immediately say that N is composite if (N%M) is 0 or has a factor in common with M.

You used 6, the product of 2 and 3. Of the possible moduli 0, 1, 2, 3, 4, 5, only 1 and 5 don't have a factor of 2 or 3.

There's nothing particularly special about 6, though -- you can do the same trick with any modulus, although you want to make it a product of small primes to maximize the density of composite moduli.

Note that, after making this check (as gnasher indicates), you only need to test trial divisors that do NOT have a factor in common with M.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
1

The general method here is called Wheel Factorization. The simplest wheel is to treat 2 specially and just test odd numbers thereafter: the 2-wheel. The next simplest is the 2,3-wheel, which you mention in your question. @gnasher729 gives the numbers for the 2,3,5-wheel above.

You can generate the numbers for a 2,3-wheel by alternately adding 2 and 4, starting from 5.

Pseudocode:

boolean isPrime(num)

  // Deal with factor 2.
  if (num MOD 2 = 0) then
    return (num = 2)
  endif

  // Deal with factor 3.      
  if (num MOD 3 = 0) then
    return (num = 3)
  endif

  // Factors >= 5.
  limit <-- 1 + sqrt(num)
  trialFactor <-- 5
  step <-- 2
  while (trialFactor < limit) do
    if (num MOD trialFactor = 0)
      // Number not prime
      return false
    endif
    trialFactor <-- trialFactor + step
    step <-- 6 - step
  endwhile

  // Number is prime here.
  return true

end

This uses less memory than a Sieve, but is too slow for very large primes.

rossum
  • 15,344
  • 1
  • 24
  • 38