# Python highest prime factor problem.

1. Feb 18, 2012

### rollcast

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. The attempt at a solution

Code (Text):
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.

2. Feb 18, 2012

### 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?

3. Feb 18, 2012

### Ninty64

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

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

4. Feb 19, 2012

### rollcast

I tried re writing the code but it didn't help as it still prints the non - prime factors?
Code (Text):
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 :

5. Feb 19, 2012

### kai_sikorski

You haven't fixed the problem Ninty mentioned.

6. Feb 19, 2012

### rollcast

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

7. Feb 19, 2012

### 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 wanna find the smallest number in it.

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

Code (Text):

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.

8. Feb 19, 2012

### rollcast

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?

9. Feb 19, 2012

### 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.

10. Feb 19, 2012

### rollcast

Is that it now?

11. Feb 19, 2012

### kai_sikorski

Very close! What you wrote would return 2.

12. Feb 19, 2012

### rollcast

Should i equal 1?

13. Feb 19, 2012

### kai_sikorski

Yup!

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

14. Feb 19, 2012

### rollcast

Code (Text):
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

15. Feb 19, 2012

### kai_sikorski

Yup, I think that should work.