Prime testing [was Re: My backwards logic]

[Steven D'Aprano]

Denis McMahon wrote:

> Note also that when searching for factors of a number n, and starting at
> 2, you can generally stop at somewhere around n/3, 

The largest factor of N you actually need to check is sqrt(n). Every factor
of n below the square root has a corresponding factor above it, e.g. if n
equals 100, then factor 2 (below 10) corresponds to factor 50 (above 10),
so there's no need to test with numbers above the square root since you
would have already detected their partner. (No need to check whether 50 is
a factor, since you've already checked 2.)

Stopping at n/2, or n/3, does a lot more work than necessary. E.g. for n
equal to one million, we have:

py> n = 10**6
py> n/2, n/3, n**0.5
(500000.0, 333333.3333333333, 1000.0)


Even there, we can improve matters by only dividing by primes:

3, 5, 7, 9 is a waste of time, 11, 13, 15 is a waste of time, ... 

If n is divisible by 9, it is also divisible by 3; likewise if n is
divisible by 15, it is also divisible by both 3 and 5. There are only
78,498 primes below one million, compared to 499,999 odd numbers excluding
1, so if you can find away to only test against primes, you'll save a lot
of time.

But even that's not how the specialists do it. If you want to check whether
(say) 2**3000+1 is prime, you don't want to use trial division at all...


-- 
Steven