euler problem 3 unrepresentative answer in different number

Question

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

Lots of [prime factorization questions](https://stackoverflow.com/search?q=python+prime+factors) on Stack Overflow. [This one](https://stackoverflow.com/questions/15347174/python-finding-prime-factors) is nearly identical to the above. — Dennis Williamson, Nov 18 '22 at 16:35
Does this answer your question? [Python Finding Prime Factors](https://stackoverflow.com/questions/15347174/python-finding-prime-factors) — gog, Nov 18 '22 at 16:46

cafce25 · Accepted Answer · 2022-11-18T16:44:48.457

0

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

edited Nov 18 '22 at 16:44

answered Nov 18 '22 at 16:16

cafce25

15,907
4
25
31

yes, but why then 19 shows up three times? in many other numbers code works well – therealuzr Nov 18 '22 at 16:35
Because the code calculates the prime factorization and `6859 = 19 * 19 * 19` – cafce25 Nov 18 '22 at 16:39
If you run your code on 49, you will get [7, 7, 1]. In your loop you divide 49 by 7, giving 7 as a factor and leaving 7 as the remainder. Then 7 is again a factor of the remainder, leaving a final remainder of 1. – rossum Nov 19 '22 at 09:02

euler problem 3 unrepresentative answer in different number

1 Answers1