I'm trying to solve the third Project Euler problem and I'd like a little help understanding a mathematical concept underlying my tentative solution.
The question reads:
The prime factors of 13195 are 5, 7, 13, and 29.
What is the largest prime factor of the number 600851475143 ?
As a caveat, in accordance with the wishes of Project Euler I won't be providing any code, my question is centered on why a mathematical concept works.
Failed Attempt
My first algorithm looked at all the numbers from 1 through 600851475143, but was unable to complete the subsequent computations (concerning primes and factorization) due to memory constraints.
Successful Attempt
My next algorithm looked at all the numbers from 1 through $\sqrt{600851475143}$ and completed the computation successfully.
My Question
Why does evaluating $\sqrt{600851475143}$ work in this instance when I really want to evaluate up to 600851475143 ? How can I be sure this approach won't miss some factor like $2 \cdot n$ or $3 \cdot n$, when $n$ is some number between $\sqrt{600851475143}$ and 600851475143 ?
Best Answer
If a number $N$ has a prime factor larger than $\sqrt{N}$ , then it surely has a prime factor smaller than $\sqrt{N}$.
So it's sufficient to search for prime factors in the range $[1,\sqrt{N}]$, and then use them in order to compute the prime factors in the range $[\sqrt{N},N]$.
If no prime factors exist in the range $[1,\sqrt{N}]$, then $N$ itself is prime and there is no need to continue searching beyond that range.