Thread: "New" primality test/check View Single Post
2018-01-07, 19:09   #232
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by axn So your algorithm: Take odd N (which we're checking if it is prime or composite) For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime. Trial division algortihm: Take odd N (which we're checking if it is prime or composite) For all odd prime n = 3,5,7,.. < sqrt(N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.
Let's compare performance. If the number is composite, the time both take depends on their smallest prime factor p. Your algorithm takes (p-1)/2 steps, while trial division takes pi(p) - 1 steps (we're assuming an odd number), which is asymptotically p/log p. In the worst case p = sqrt(n) so yours takes O(sqrt(n)) operations and trial division takes O(sqrt(n)/log n) operations (including the cost of sieving). But gcd is more expensive than division, so really the algorithms differ by a factor more like log^2 n.

If the number is prime, your algorithm takes (n-3)/2 divisions which is O(n). Trial division needs only O(sqrt(n)/log n).

So for composites your algorithm is worse, but it's not too bad. But it's catastrophically bad on primes.