Why does my program stop working for large values?

Question

Hi I wrote this program in response to the following question:

"What is the largest prime factor of the number 600851475143?"

The program works for "composite" equal to 13195, but it does not work if I set it equal to 600851475143.

Why does this happen?

composite = 600851475143
for m in range (2,composite):
    while composite % m == 0:
        if composite / m == 1:
            break
        else:
            composite = composite / m
print(composite)

What flavor of python do you use? Your code will not do what you expect it to do in Python 3. — DYZ, Jun 18 '18 at 21:48
You've got a 600-billion-iteration outer loop. That's not going to finish quickly. — user2357112, Jun 18 '18 at 21:52
Sorry. When I say it doesn't work I mean to say that nothing happens. The program doesn't run for a sufficiently large value of "composite." — Sir know-a-ton, Jun 18 '18 at 21:52
Possible duplicate of [Python Finding Prime Factors](https://stackoverflow.com/questions/15347174/python-finding-prime-factors) — user3483203, Jun 18 '18 at 21:52
The dupe I linked uses the exact same number as your example, I'm guessing this is from an online resource somewhere — user3483203, Jun 18 '18 at 21:53
You are modifying a for loop and expecting the range to recalculate but it doesn't work like that. — Zev, Jun 18 '18 at 21:53
So my program works, but not for a sufficiently large value because of the amount of time required to carry out the calculations, right? — Sir know-a-ton, Jun 18 '18 at 21:56
@Sirknow-a-ton it would be easy to figure out what your program is doing (if it is running or not) by using basic debugging statements placed in your code. — user3483203, Jun 18 '18 at 21:57
@user3483203 Ah thank you. My program does in fact arrive at a correct answer but it was not being displayed. The program keeps running due to the conditions on the outer loop. I'll make an adjustment so that it ends after it has found an answer. — Sir know-a-ton, Jun 18 '18 at 22:05

score 2 · Answer 1 · answered Jun 18 '18 at 21:58

The issue is the combination this line:

for m in range (2,composite):

and this line:

    composite = composite / m

Range won't recalculate while you are looping. See this question for more details: Changing the number of iterations in a for loop

Instead, your code should be the following (to fix that issue):

composite = 600851475143

m = 2
while m < composite:
    while composite % m == 0:
        print(composite, m)
        if composite / m == 1:
            break
        else:
            composite = composite / m
    m += 1
~

Why does my program stop working for large values?

1 Answers1