so. i've been trying to solve a Euler's problem #3
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
my knowledge is low. so i came here and found a perfect solution which takes only 140ms for the number in the problem (600851475143) my guess was that for the number that so high should be at least few higher prime factors (as i understood later not necessary). anyways i was happy but start to try some other numbers to check their largest prime factor. and also i've tried a number 6859 and python outputs me next (following code will be at the end): 1 [19, 19, 19, 1]
for the 600851475143 number it's correct answer: 6857 [71, 839, 1471, 6857]
so for the 13195 number: 29 [5, 7, 13, 29]
and the code:
# n = 600851475143
n = 6859
i = 2
b = []
while i * i < n:
while n % i == 0:
n = n / i
b.append(i)
i += 1
b.append(int(n))
print(int(n))
print(b)
my question is why 6859 number outputs so strange answer (three times 19 and then 1) and second question: why and how this code outputs only prime factors, 'cuz that's what im not get at all and maybe the last question is why exactly this code works so fast (in comparison to others)
nothing, just trying to understand the code
The reason the code appends a 1 at the end for 6859 is that the last prime factor is contained multiple times and so the inner while loop runs until n == 1
You could fix the code by adding a check if n is different from 1 before you add it like so:
n = 6859
i = 2
b = []
while i * i < n:
while n % i == 0:
n = n / i
b.append(i)
i += 1
if n != 1:
b.append(int(n))
print(int(n))
print(b)
The reason you're getting only prime factors is because if i isn't prime then n will have been divided by all factors smaller than i and thus n can't be divisible by i