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.
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.