The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
First prime problem, we all love primes, ahh?
1) Simply brute force:
Try to divide out the number with every integer from 2 to the number, the last divisible number is the factor we want.
2) Optimization tip:
Since 2 is the only even prime, so check odd numbers only.
3) More optimization trick:
Notice there's no factor of n larger than the square root of n, so set the limit to the square root of n instead of n.
P.S. Many languages doesn't have built in square root function, though you can simply compute the squared of the attempting factors, i.e. i*i < n.
[GitHub Link] [Official overview pdf by projecteuler.net]
1) Simply brute force:
Try to divide out the number with every integer from 2 to the number, the last divisible number is the factor we want.
2) Optimization tip:
Since 2 is the only even prime, so check odd numbers only.
3) More optimization trick:
Notice there's no factor of n larger than the square root of n, so set the limit to the square root of n instead of n.
P.S. Many languages doesn't have built in square root function, though you can simply compute the squared of the attempting factors, i.e. i*i < n.
[GitHub Link] [Official overview pdf by projecteuler.net]