Project Euler 3 in Python 3.5.2

Asked Sep 18 '16 at 15:12

Active Sep 18 '16 at 17:32

Viewed 82 times

The Project Euler #3 asks for the largest prime factor of a given number, which I have named num2.

I have already solved this problem using:

i = 2

while num2 != 1:
    if num2 % i == 0:
        num2 /= i
    else:
        i += 1

print(i)

But I found this code that I cannot understand:

i = 2

while num2 > i ** 2:
    while num2 % i == 0:
        num2 = num2 // i
    i = i + 1

print(num2)

Can someone explain to me why it checks for num2 > i * i?

edited Sep 18 '16 at 17:32

linusg

asked Sep 18 '16 at 15:12

Larrrrrrrrrry

3

There is no point in checking for all values of `i`; once `i` is bigger than the square root of `num2` it can't be a prime factor of `num2` anymore. – Martijn Pieters Sep 18 '16 at 15:13
@cricket_007: the input number to the problem, one would presume. – Martijn Pieters Sep 18 '16 at 15:15
num2 is just the string name of the given number. I have set num2 = 600851475143. – Larrrrrrrrrry Sep 18 '16 at 15:15
Thanks for the dup link and the comments , I think I understand it now. – Larrrrrrrrrry Sep 18 '16 at 15:17
Some references: [Why do we check up to the square root of a prime number to determine if it is prime or not](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) /// [Prime numbers](https://en.wikipedia.org/wiki/Prime_number) /// [Integer factorization](https://en.wikipedia.org/wiki/Integer_factorization) – Frank Kair Sep 16 '17 at 21:49

0 Answers0