Euler 3 - prime numbers

http://projecteuler.net/problem=3

Hi all, here's where the projects start requiring some thought, and often some research.

What is the largest prime factor of the number 600851475143?



Here's the gist.
it's easier to find the lowest prime factor, divide the number by it, and repeat.

e.g. if a number X is the product of prime factors A x B x C
Then, if the lowest prime factor is A, you now have X/A = B x C
Repeat finding the lowest prime factor of X/A and you'll get B.
Now you have to find the lowest prime factor is (X/A)/B.

X=AxBxC
X/A=(A/A)xBxC
(X/A)/B=(A/A)x(B/B)xC
(X/A)/B =C <= the largest prime factor.

So, how do you find a prime factor? well, for starters, it's a prime number.
We start by looking through a list of numbers - 2, 3, 5, 7, 11, 13, 17 etc.. to see if X is divisible by any.

Lets start by setting boundaries - how high should we count?
If we want the prime factors of 91 (i.e. 7x13).
We wont get past 7 before dividing.  i.e. we'll count up to the lowest prime factor. 

AxB=C. 
If A gets bigger, B must get smaller. So we'll iterate up to B and then divide according to the algorithm. The maximum iterations will then be when A=B and this is the square root of C.

The largest prime factor will be the number itself - i.e. it is prime. Well, how do we know? Once again, we only need to count up to the square root.
e.g. what's the prime factors of 31?
we'll check, 2, 3, 5, 7- we've went past the square root and stop here. Why? Well, since we've past the square root, the other number must be smaller - and if prime would have been counted already! 31/7 ~ 4.43. We've already checked smaller primes, so we know they aren't going to divide it.

The checks look like this:
AxB=C
2x31/2=31...2x15.50=31...A=2, B=15.5
3x31/3=31...3x10.33=31...A=3, B=10.33
5x31/5=31...5x 6.20=31...A=5, B=6.2
7x31/5=31...7x 4.43=31...A=7, B=4.43

So stop checking. Increasing A just makes B cover the number range we already went through, so the number is prime.

So - iterate over primes to find the first prime factor, range of primes from 2 to the square root of the number.

Great - how do you know what IS prime anyway? You're testing primes only right? why not test 4 or 9 and see if out number is divisible by that?

Well, here's where we create an array to keep in mind what's prime or not.
e.g. 
Lets say we wanted to know the prime factors of 221. The Square root is ~14.9, so we only need to check up to there.

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Prime numbers and the number 2, are odd. So do a check for 2, then iterate over the odds. no point spending half your time checking even numbers. if it's not divisible by 2, then it's not divisible by any even number.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 xx 00 00 00 00 00 00 00 00 00 00 00 00 00

Now check 3. It's not divisible by 3, so mark off every multiple of 3 as not a factor.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 xx xx 00 00 xx 00 00 xx 00 00 xx 00 00 xx
See what happened? Now I didn't mark off evens before since there's no point of bothering to check. 

Last check was 3. Add 2, and check 5 - was 5 marked? No? ok! 5 is not a factor, we lose 5 and 10.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 xx xx 00 xx xx 00 00 xx xx 00 xx 00 00 xx

7 Isn't a factor, so we mark out 7 and 14.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 xx xx 00 xx xx xx 00 xx xx 00 xx 00 xx xx


Next odd number is 9 but that's marked. so skip it. next odd number is 11.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
00 xx xx 00 xx xx xx 00 xx xx xx xx 00 xx xx


Not a factor.  Next is 13 - that's a factor!

Factors are 13 + the factors of 221/13 - which means it's 13 and factors of 17. We'd do the same check on 17 as illustrated above and return no prime factor found (meaning the number itself is prime).


Now optimizations. We can check 2 initially, and there's no need to store even number flags if they're not being checked.

So our array can be half the size.
00 01 02 03 04 05 06 07 08 ==>N
03 05 07 09 11 13 15 17 19 ==>2N+3

If we're looking at a possible prime factor in the array - say 11, it corresponds to (11-3)/2 = 4 in the index for the flag.

So we're only counting up to the square root of a number, and we're skipping every even number to look for a factor.