Calculating the prime factors of a very big integer

user_14904063 0
Viewed 64

I am having an interesting problem with Python. My task is to calculate all prime factors of a given number. This is my code:

import math

def func(number):
    while number % 2 == 0:
        number = number / 2
        print("2")

    for i in range(3, math.ceil(math.sqrt(number)) + 1, 2):
        while number % i == 0:
            number = number / i
            print(i)

    if number > 2:
        print(str(int(number)))

Normally this code works and there is no problem. However, say we pass 211,111,122,222,223,420 to func. It will print these factors: 2, 2, 2, 2, 2, 2, 19, 97, 178980536338. This obviously can't be true as the number whose factors we want to find ends with zero, which means that it must have at least one 5 among its factors. Right? In fact, if you multiple the printed factors, the result will be 211,111,122,222,223,424 (four units more than the passed number). What am I doing wrong?

prime-factoring math python
1 Answers

Use // instead of /. In Python 3, the / operator gives you a float, which introduces inaccuracies. If you use // instead, you will stick with ints, which gives you the right answer.

def func(number):
    while number % 2 == 0:
        number = number // 2
        print(2)
    for i in range(3, math.ceil(math.sqrt(number)) + 1, 2):
        while number % i == 0:
            number = number // i
            print(i)
    if number > 2:
        print(number)

func(211111122222223420)

gives

2
2
5
1181
1321
1747
3872893
user_38906320
Related