Python not incrementing a loop as I expected

Question

I have a bit of code which will take an integer as an input and print out a sorted list of that integers prime factors.

It works perfectly for pretty much all numbers, for example when the input is 100 it will print [2, 2, 5, 5] and for 1235632 it will spit out [2, 2, 3, 3, 343237].

However for far larger numbers it will not print the factors out in order, I am not sure if this is an unresolved issue in the code I have overlooked or if it is something else.

For instance when I put in 1234567891011121314151617 it will output [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 43, 109, 104281, 1394027], which is obviously not sorted and I cannot for the life of me figure out why.

I am using what I think is the most recent version of pycharm.

Anyway, this is the code:

from math import floor
from math import sqrt

n = int(input("Enter a number to be split into its prime factors"))
FList = []
k = 1

while n != 1:
    k = k + 1
    s = floor(sqrt(n))

    if k > s:
        FList.append(int(n))
        break

    if n % k == 0:
        n = n/k
        FList.append(k)
        k = 1

print(FList)

Edit: Just to clarify I would rather fix the program as it is then use a sorting algorithm to help clean up.

As pointed out by someone else, the factors of the large number are complete garbage so I guess the current question is now why it prints those numbers.

The product the numbers in that last array is 1234567891011121270751232... I think your problem lies elsewhere — MoxieBall
– MoxieBall, Commented Jul 20, 2018 at 18:34
You might want to simplify your code a bit, it looks like n is doing quite a bit of work here and the reuse of variable might be causing problems. Try giving variables more descriptive names and using each variable strictly for one purpose. — shayaan
– shayaan, Commented Jul 20, 2018 at 18:38
Your code gives a wrong output: your last large number is odd, so 2 can't be one of its factors. — Thierry Lathuille
– Thierry Lathuille, Commented Jul 20, 2018 at 18:43
Thanks for that spot about how the 2 can't be a factor, the program seems to work for numbers such as 12312456 and 12312457 which I have double checked to be correct but I have no idea why it doesn't work for that number. — DonGiovani4761
– DonGiovani4761, Commented Jul 20, 2018 at 19:03

Thierry Lathuille · Accepted Answer · 2018-07-20 19:08:04Z

The problem is that you're using / for division, whose result is a float:

6/2
# 3.0

When you try to factor your large number, the result you get after dividing by the first factor (3) is:

1234567891011121314151617 / 3
# 4.115226303370404e+23

which is rounded, as floats have a limited precision. That's why you can now divide it by 2 a lot of times.

You should use integer division //, which would give you the exact quotient with unlimited precision:

1234567891011121314151617 // 3
# 411522630337040438050539

So, just change your code to:

from math import floor
from math import sqrt

n = int(input("Enter a number to be split into its prime factors"))
FList = []
k = 1

while n != 1:
    k = k + 1
    s = floor(sqrt(n))

    if k > s:
        print('appending', n)
        FList.append(int(n))
        break

    if n % k == 0:
        n = n//k  # Use integer division here
        FList.append(k)
        k -= 1  # Try k again on next loop, no need to test smaller values again.

print(FList)

For the number you tried, there a some large factors, so that could take much time...(actually, it's 3*2*47*4993*584538396786764503...)

jfleach · Accepted Answer · 2018-07-20 18:35:21Z

0

You could use sorted to print the list in order.

print(sorted(FList))

answered Jul 20, 2018 at 18:35

jfleach

5132 gold badges8 silver badges24 bronze badges

2 Comments

Thierry Lathuille Over a year ago

This wouldn't solve the problem, just reorder a wrong result, see my answer.

DonGiovani4761 Over a year ago

Sorry forgot to mention in the post that I didn't want to rely on any sorting function seeing as it works fine for smaller numbers perfectly but not larger ones.

Collectives™ on Stack Overflow

Python not incrementing a loop as I expected

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related