1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python highest prime factor problem.

  1. Feb 18, 2012 #1
    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. jcsd
  3. Feb 18, 2012 #2

    kai_sikorski

    User Avatar
    Gold Member

    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?
     
  4. Feb 18, 2012 #3
    Edit: Oops, didn't realize someone posted before me.

    There's a while loop there that you forgot to reinitialize :wink:
     
  5. Feb 19, 2012 #4
    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 :
     
  6. Feb 19, 2012 #5

    kai_sikorski

    User Avatar
    Gold Member

    You haven't fixed the problem Ninty mentioned.
     
  7. Feb 19, 2012 #6
    I can't see why it shouldn't work unless I have messed up the indenting for the j while loop?
     
  8. Feb 19, 2012 #7

    kai_sikorski

    User Avatar
    Gold Member

    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.

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

    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.
     
  9. Feb 19, 2012 #8

    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?
     
  10. Feb 19, 2012 #9

    kai_sikorski

    User Avatar
    Gold Member

    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.
     
  11. Feb 19, 2012 #10
    Is that it now?
     
  12. Feb 19, 2012 #11

    kai_sikorski

    User Avatar
    Gold Member

    Very close! What you wrote would return 2.
     
  13. Feb 19, 2012 #12
    Should i equal 1?
     
  14. Feb 19, 2012 #13

    kai_sikorski

    User Avatar
    Gold Member

    Yup!

    Okay so now look at your code. You basically have a very similar mistake.
     
  15. Feb 19, 2012 #14
    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
     
  16. Feb 19, 2012 #15

    kai_sikorski

    User Avatar
    Gold Member

    Yup, I think that should work.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook