Finding prime factors by taking the square root

Question

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 ?

Answer 1

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.

Answer 2

What you're describing is a prime-testing algorithm known as the sieve of Eratosthenes.

It seems like you already understand the concept:

• Cross out $1$

• Circle $2$ as the first prime, then cross out all of the multiples of $2$ in your list.

• The next not-crossed-out number is the next prime (in this case $3$).

If your list has $N$ numbers, you only need to test until you get to a prime that's bigger than $\sqrt{N}$.

---

Other users have mentioned the reason for $\sqrt{N}$ being the maximum you need to test until, but I'll add an alternative explanation. If you consider listing out all of the factors of $N$, in order from least to greatest, you will either get an even number or an odd number. $N$ has an odd number of factors if and only if it is a perfect square.

In any case, $N$ always has the same number of factors (strictly) less than its square root as it does (strictly) greater than its square root.

In fact, there's an explicit bijection between the set of factors less than $\sqrt{N}$ and the set of factors greater than $\sqrt{N}$ given by $$f(a) = \frac{N}{a}$$

(where $a$ is a factor of $N$ less than $\sqrt{N}$)

Answer 3

If you do not find a factor less than $\sqrt{x}$, then $x$ is prime for the following reason. Consider the opposite, you find two factors larger than $\sqrt{x}$, say $a$ and $b$. But then $a\cdot b> \sqrt{x}\sqrt{x} = x$. Therefore, if there is a factor larger than $\sqrt{x}$, there must also exist a factor smaller than $\sqrt{x}$, otherwise their product would exceed the value of $x$.

Regarding the last question. You will not miss some factor like $2\cdot n$ because you have already checked if $2$ is a factor.