Python highest prime factor problem.

[rollcast]

Homework Statement

The problem is taken straight from the Project Euler website:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

The answer is 6857 as I must have solved it before but I can't figure out how I worked it out.

Homework Equations

The Attempt at a Solution

from math import *

number = 600851475143
number_sqrt = sqrt(number)
i = 1
j = 2
highest_prime_factor = 0

while i < number_sqrt:      #Loops while i is less than the square root of number
    if number % i == 0:     #Tests if i is a factor of number
        while j <= sqrt(i):     #Loops while j is less than square root of i
            is_prime = 1

            if i % j == 0:      #Tests if i is prime
                is_prime = 0
                break

            if j == trunc(sqrt(i)) and is_prime == 1:       #Checks if loop is finished and if i is prime
                highest_prime_factor = i        #Sets variable for highest prime factor as i

            j += 1
    i += 1

print highest_prime_factor

I'm not sure what wrong with my code but it seems to be printing the highest factor of the number.

 

[kai_sikorski]

I think your code is probably printing the SECOND highest factor of the number, provided the highest factor wasn't a prime. Can you tell why that would happen?

 

[Ninty64]

Edit: Oops, didn't realize someone posted before me.

There's a while loop there that you forgot to reinitialize

 

[rollcast]

I tried re writing the code but it didn't help as it still prints the non - prime factors?

import math

number = 600851475143
i = 2
j = 2
while i <= math.trunc(math.sqrt(number)):       #Loops while i is less than or equal to the square root of number
    if number % i == 0:     #Tests if i is a factor of number
        while j <= math.sqrt(i):        #Loops while j is less than or equal to the square root of i
            is_prime = 1
            if i % j == 0:  #Tests if j is a factor of i - breaks loops if true
                is_prime = 0
            if is_prime == 1 and j == math.trunc(math.sqrt(i)):        #Tests if j is not a factor i and if the loop if finished
                print i
            j += 1      #Increments j
    i += 1      #Increments i

The results it prints :

[Dbg]>>>
71
839
1471
6857
59569
104441
486847

 

[kai_sikorski]

You haven't fixed the problem Ninty mentioned.

 

[rollcast]

You haven't fixed the problem Ninty mentioned.

I can't see why it shouldn't work unless I have messed up the indenting for the j while loop?

 

[kai_sikorski]

Okay here is an example pseudo code that has the a similar problem to your code. Say I get a 2d array and I want to find the smallest number in it.

$$A = \left(<br /> \begin{array}{ccccc}<br /> 10 & 9 & 7 & 0 & 9 \\<br /> 6 & 10 & 6 & 2 & 7 \\<br /> 3 & 2 & 5 & 8 & 10 \\<br /> \end{array}<br /> \right)$$

N = 3 #number of rows
M = 5 #number of columns
smallest = A[SUB]11[/SUB]
i = 2
j = 1
[b]while[/b](j ≤ M)
    [b]while[/b](i ≤ N)
        [b]if[/b] A[SUB]ij[/SUB]<smallest
            smallest = A[SUB]ij[/SUB]
        [b]end[/b]
        i = i+1;
    [b]end[/b]
    j = j+1;
[b]end[/b]

This code would spit out 3. If you can fix this code you should be able to fix yours.

 

[rollcast]

Okay here is an example pseudo code that has the a similar problem to your code. Say I get a 2d array and I want to find the smallest number in it.

$$A = \left(<br /> \begin{array}{ccccc}<br /> 10 & 9 & 7 & 0 & 9 \\<br /> 6 & 10 & 6 & 2 & 7 \\<br /> 3 & 2 & 5 & 8 & 10 \\<br /> \end{array}<br /> \right)$$

N = 3 #number of rows
M = 5 #number of columns
smallest = A[SUB]11[/SUB]
i = 2
j = 1
[b]while[/b](j ≤ M)
    [b]while[/b](i ≤ N)
        [b]if[/b] A[SUB]ij[/SUB]<smallest
            smallest = A[SUB]ij[/SUB]
        [b]end[/b]
        i = i+1;
    [b]end[/b]
    j = j+1;
[b]end[/b]

This code would spit out 3. If you can fix this code you should be able to fix yours.

I'm not certain but is there an extra end in that code?

The red end breaks the red while loop and the blue one breaks the blue while loop, but the green one causes it to break early?

 

[kai_sikorski]

No I meant the end to go with the if.

The idea in the code is to fix the column, step over all the rows, then go to the next column and step over all the rows.. etc. But it does do that. Why not? Try pretending you're the computer and going through the algorithm step by step. Where does it go wrong.

 

[rollcast]

Okay here is an example pseudo code that has the a similar problem to your code. Say I get a 2d array and I want to find the smallest number in it.

$$A = \left(<br /> \begin{array}{ccccc}<br /> 10 & 9 & 7 & 0 & 9 \\<br /> 6 & 10 & 6 & 2 & 7 \\<br /> 3 & 2 & 5 & 8 & 10 \\<br /> \end{array}<br /> \right)$$

N = 3 #number of rows
M = 5 #number of columns
smallest = A[SUB]11[/SUB]
j = 1
[b]while[/b](j ≤ M)
    i = 2
    [b]while[/b](i ≤ N)
        [b]if[/b] A[SUB]ij[/SUB]<smallest
            smallest = A[SUB]ij[/SUB]
        [b]end[/b]
        i = i+1;
    [b]end[/b]
    j = j+1;
[b]end[/b]

This code would spit out 3. If you can fix this code you should be able to fix yours.

Is that it now?

 

[kai_sikorski]

Very close! What you wrote would return 2.

 

[rollcast]

Very close! What you wrote would return 2.

Should i equal 1?

 

[kai_sikorski]

Should i equal 1?

Yup!

Okay so now look at your code. You basically have a very similar mistake.

 

[rollcast]

import math

number = 600851475143
i = 2
while i <= math.trunc(math.sqrt(number)):       #Loops while i is less than or equal to the square root of number
    if number % i == 0:     #Tests if i is a factor of number
        j = 2
        while j <= math.sqrt(i):        #Loops while j is less than or equal to the square root of i
            is_prime = 1
            if i % j == 0:  #Tests if j is a factor of i - breaks loops if true
                break
            if is_prime == 1 and j == math.trunc(math.sqrt(i)):        #Tests if j is not a factor i and if the loop if finished
                print i
            j += 1      #Increments j
    i += 1      #Increments i

 

[kai_sikorski]

Yup, I think that should work.