Largest Prime Factor of 600851475143

[Arman777]

Homework Statement

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Homework Equations

The Attempt at a Solution

Here part of the my code

#!/usr/bin/python
import math
N=99
for n in range (2,N):
     if N%n == 0:
         for y in range (2,n+1):
             n%y!=0
         print(n)

When I do this it prints these values;
3,9,11,33
I can't understand why ? Why 9 and 33 keeps coming ? Note: I am doing it first on small numbers to test the code.

 

[QuantumQuest]

Taking into account some of your recent posts I'll just recommend either writing first pseudocode to see exactly what language constructs, in what way to use them and what operations you must do or write first comments about what you're doing and then implement them in the programming language you use. This second is oftentimes given as a method in some schools / curricula.

 

[Arman777]

Taking into account some of your recent posts I'll just recommend either writing first pseudocode to see exactly what language constructs, in what way to use them and what operations you must do or write first comments about what you're doing and then implement them in the programming language you use. This second is oftentimes given as a method in some schools / curricula.

Okay I ll try, and I noticed that this code is not a good one since takes a lots of time to chechk everything. I ll try to square root method.

 

[QuantumQuest]

I think its vecause of the print position...or Idk maybe I am tired that's why I don't see it for now.

That's why I gave this advice. If you write first pseudocode or put a comment about what the final loop is doing for instance, you'll come to think what to print and where. As the programs you write become more complex, it will be very difficult to keep track of what you're doing and much more as time progresses for each program you write. Also getting tired and not seeing even the obvious sometimes is something that all programmers experience. You have always to take a rest in this case.

 

[Arman777]

That's why I gave this advice. If you write first pseudocode or put a comment about what the final loop is doing for instance, you'll come to think what to print and where. As the programs you write become more complex, it will be very difficult to keep track of what you're doing and much more as time progresses for each program you write. Also getting tired and not seeing even the obvious sometimes is something that all programmers experience. You have always to take a rest in this case.

Thanks, then I ll try again later on and If I still can't solve I ll post it.

 

[Mark44]

for y in range (2,n+1):
      n%y!=0

The body of your for loop here does nothing useful. For each value of y from 2 through n, it evaluates the expression n % y and compares it to 0. Since you aren't doing anything with the value (which will be either true or false), that line of code might as well not be there. It's sort of like asking someone, "Is today Sunday?" but walking away before you hear their answer.
For that matter, the whole loop could be removed with no change in how your program runs.

 

[Arman777]

The body of your for loop here does nothing useful. For each value of y from 2 through n, it evaluates the expression n % y and compares it to 0. Since you aren't doing anything with the value (which will be either true or false), that line of code might as well not be there. It's sort of like asking someone, "Is today Sunday?" but walking away before you hear their answer.
For that matter, the whole loop could be removed with no change in how your program runs.

I didn't like my pre-code.Now I have another idea but I don't know how to create a loop for it. Maybe its due to my knowledge but here is my idea,

So let's suppose we have N=99 then I will divide it by numbers starting from 2. I cannot divide it 2 but I can divide it 3 so 99/3=33 so let's start to do the same thing. I cannot it divide 2 but three then I have 33/3=11 now the same thing for this but since its a prime I cannot divide it perfectly so largest prime is 11. No we can do it for 141 we can divide it 3 and we get 47 since 47 cannot divide any number we have a largest prime factor of 141.

So here is my code for that

#!/usr/bin/python
import math
N=20
for n in range (2,N+1):
    if N%n==0:
        b=N/n

so here the values of b are 10,5,4,2 etc
Is there a way to stop it after the first result is getting or should I pick it (from an array for example)
The second part is I have to do the same thing for b but the thing is I cannot return in other words I can't make a loop for it.

 

[Mark44]

You're looking for primes, so for a particular value of n, if N % n == 0, then you know that N isn't prime, and you can stop looking. One way to get out of the loop is to use the break statement.

N = 20
for n in range(2, N + 1):
   if N % n == 0;
      b = N/n
      break

The break statement terminates the nearest enclosing loop, which in this case is the "for n in range(2, N + 1)" loop.

If no values of n are such that N % n == 0, the break statement won't be executed.

 

[Arman777]

You're looking for primes, so for a particular value of n, if N % n == 0, then you know that N isn't prime, and you can stop looking. One way to get out of the loop is to use the break statement.

N = 20
for n in range(2, N + 1):
   if N % n == 0;
      b = N/n
      break

The break statement terminates the nearest enclosing loop, which in this case is the "for n in range(2, N + 1)" loop.

If no values of n are such that N % n == 0, the break statement won't be executed.

Break helps but I can't move to next loop from the break which that doesn't help me much..

 

[Mark44]

Break helps but I can't move to next loop from the break which that doesn't help me much..

There is no next loop in the code I posted.

N = 20
for n in range(2, N + 1):
   if N % n == 0;
      b = N/n
      break
print("b = ", b)

When n == 2, the if expression is true, so b gets set to 10, and the break statement terminates the for loop. This causes the print statement to execute, displaying "b = 10". Note that if N had been set to 19 all of the values of n from 2 through 19 would be tested, with only 19 % 19 being equal to zero. In this case, b gets set to 1. The print statement will always execute. What the break statement does is to terminate the loop early in some instances.

 

[Arman777]

There is no next loop in the code I posted.

N = 20
for n in range(2, N + 1):
   if N % n == 0;
      b = N/n
      break
print("b = ", b)

When n == 2, the if expression is true, so b gets set to 10, and the break statement terminates the for loop. This causes the print statement to execute, displaying "b = 10". Note that if N had been set to 19 all of the values of n from 2 through 19 would be tested, with only 19 % 19 being equal to zero. In this case, b gets set to 1. The print statement will always execute. What the break statement does is to terminate the loop early in some instances.

Okay so now we have 10 then I have to do this steps in a loop so that I can get 5 ? I mean I need a big general loop so that it does this step every time automatically

like this

#!/usr/bin/python
N=20
while
for n in range (2,N+1):
    if N%n==0:
        b=N/n
        break
for y in range (2,b+1):
    if b%y==0:
        t=b/y
        break
print(t)

another awkward thing is this works well in pythontutor but not when I run it normally.
it gives float error on "for y in range (2,b+1):"

The thing is N that we want to calculate is so large so I have to do this main step

for n in range (2,N+1):
    if N%n==0:
        b=N/n
        break

in a loop. I don't know if there's a fast way but this seemed to me the fastest for a such large number.

Edit: It woıks well on 2.7 but not in 3.6 which that's another awkward thing

 

[Arman777]

Okay I solved the float problem. but I need to solve the loop problem for now

"for y in range (2,int(b)+1):" works well

 

[Mark44]

I don't understand why you have two loops. Since you're just trying to find out whether a number is prime, if N % n == 0 for some value of n, then N isn't prime. It seems that you are trying to find all the factors of a number, rather than just to determine whether the number is prime.

For the float error, use integer division: b = N // n

For example 6/4 == 1.5, but 6//4 == 1. Python has two different operators for division -- / for ordinary floating point division, and // for integer division. Other languages, such as C, C++, C#, and Java, have just a single operator /. The context is enough to tell which kind of division to use. For example, in C, etc. 6/4 == 1 while 6.0/4 == 1.5.

 

[Arman777]

Since you're just trying to find out whether a number is prime, if N % n == 0 for some value of n, then N isn't prime. It seems that you are trying to find all the factors of a number, rather than just to determine whether the number is prime.

Yes the question is not about if N is prime or not but,

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

Like as we did If I put 20 I get 10, 10 is not a prime number.

 

[Arman777]

For example If I put N=100 in this code it stops at 25

#!/usr/bin/python
N=100
for n in range (2,N+1):
    if N%n==0:
        b=N//n
        break
print(b)
for y in range (2,b+1):
    if b%y==0:
        t=b//y
        break
print(t)

but it should have go till 5 since its the largest prime factor.

or for 141 it says 47 and 1 which it means 47 is the largest prime factor etc. but as I said if its have more then 2 steps then it will not show us (the case of 100) so we need to loop the part.

 

[Mark44]

For some reason, I was thinking that you wanted to just see if a number was prime, even though you said in your first post that you wanted to find the largest prime factor. Try this:

N=100
list = []
for n in range (2,N+1):
   if N % n == 0:
       b = N//n
       list.append(b)
print(list)

Note: it's good programming practice to insert some whitespace in you code -- makes it easier to read. For example if N % n == 0:is better than if N%n==0;

When the code above runs, the largest prime factor will be the first one in list.

 

[Arman777]

the largest prime factor will be the first one in list.

50 is not a prime ? I can list the factors (which that's what I did in the first place)

But I think other then loop method, by using this array I can find the largest prime number. I am thinking on it

 

[Mark44]

Doh! I'm just not thinking right today! Sorry!

You could use the code I wrote to fill an array with all the factors, and then loop through each factor in the array to see if it is prime. The list method len() returns the number of items in a list.

It would be helpful to you to come up with an algorithm or write pseudocode as to how you plan to do this.

 

[Mark44]

@Arman77, considering that you want to find the largest prime factor of, say, 600851475143, I think that you should reconsider your strategy. Dividing this number successively by 2, 3, 4, and so on is very inefficient. There was a suggestion made earlier about square roots that would be useful in this problem.

Here's an example using a smaller number -- 84. $\sqrt {84}$ is a bit over 9, so it doesn't make sense to check for divisors that are larger than 9. It's true that 42 is a divisor, but the other factor is 2, so check all divisors from 2 through 9 will find all pairs of numbers that multiply to 84.
For 600851475143, you need to check the divisors only up to $\sqrt{600851475143} \approx 775,146$ for the same reason as given above.

Here's an outline of how you might code this:
Note: Edited from earlier version
For each integer n from 2 through M (= sqrt(N))
Determine whether n divides N
If so, determine whether N/n is prime.
If N/n is prime, you're done, since N/n will be the largest prime factor. (All other factors will be smaller.)
Otherwise (M/n isn't prime) start a new loop iteration.

BTW, if you know how to write functions in Python, "determine whether M/n is prime" would be an excellent candidate for a user-written function. It would have two parameters, M and n, and would return either true or false, depending respectively on whether M/n is prime or not.

 

[Arman777]

Here's an example using a smaller number -- 84. √8484\sqrt {84} is a bit over 9, so it doesn't make sense to check for divisors that are larger than 9. It's true that 42 is a divisor, but the other factor is 2, so check all divisors from 2 through 9 will find all pairs of numbers that multiply to 84.
For 600851475143, you need to check the divisors only up to √600851475143≈775,146600851475143≈775,146\sqrt{600851475143} \approx 775,146 for the same reason as given above.

I thought that, but for example If I take 99, sqrt(99)=9.94 so in this sense I shouldn't check larger then 9 (or 10) but 11 is the largest prime factor of 99, so I don't think that works in general.

I managed to create a code actually. Its kind of complex, but sad thing is I couldn't manage to work it (it takes more then 1000 steps, so when I run it nothing happens)

#!/usr/bin/python
N=600851475143
v=[]
for n in range (2,N+1):
   if N%n==0:
      b=N//n
      v.append(b)
      if v[len(v)-1]==1:
            v.reverse()
            for t in range (3,len(v)):
               for y in range (2,len(v)):
                   v[t]%v[y]!=0
               break
print (v[t])

Also for t it stuckes at t=3 and doesn't move when y=len(v) (it stops calculating) but in any case this is not an efficient way to solve the problem.

Here the main problem is, I am losing too many steps (time) when I try to calculate the factors of N. I should find another way...

@Arman77, considering that you want to find the largest prime factor of, say, 600851475143, I think that you should reconsider your strategy. Dividing this number successively by 2, 3, 4, and so on is very inefficient. There was a suggestion made earlier about square roots that would be useful in this problem.

Yes you are right.
I thought that even it takes more steps it will give me something.

Maybe if we can fix the problem in t then we can find the right solution after some time ?

Edit:Another sad thing is this is the 3rd problem in the project euler site

 

[Mark44]

I thought that, but for example If I take 99, sqrt(99)=9.94 so in this sense I shouldn't check larger then 9 (or 10) but 11 is the largest prime factor of 99, so I don't think that works in general.

But when you check to see if 9 divides 99, it does, and the other factor is 11.

For each integer n from 2 through M (= sqrt(N))
Determine whether n divides N
If so, determine whether N/n is prime.

So in this case, with n = 9 and N = 99, N/n = 11, and you need to check whether 11 is prime.

Here the main problem is, I am losing too many steps (time) when I try to calculate the factors of N. I should find another way...

A simple speedup would be this: after you check to see if 2 divides N, don't divide by any other even numbers. This alone will cut the number of iterations in half, since you won't be checking 4, 6, 8, 10, etc. There are other things you can do to speed things up. All of them will make your code more complicated, but it will run faster. That's the tradeoff -- more complex code versus faster running time.

 

[Vanadium 50]

I've calculated the answer. Based on the answer, I would suggest you do the following:

1. Write in pseudocode, not Python. Turn it into Python later. I know you've heard this before, and kept going in Python. Bad idea.
2. Look at the sqrt(N). Big number. You don't want to check that many numbers when you have found all the factors. So think about how to terminate the program.
3. Do not try and make the program faster by testing divisibility against only prime numbers.

 

[Arman777]

So in this case, with n = 9 and N = 99, N/n = 11, and you need to check whether 11 is prime.

Hmm what abou 141 ? the root is nearly 12 but the largest prime factor is 47 so how can we get it ?

I've calculated the answer

What did you used for the code ? or I should say what kind of approach ?

• Look at the sqrt(N). Big number. You don't want to check that many numbers when you have found all the factors. So think about how to terminate the program.

• Do not try and make the program faster by testing divisibility against only prime numbers.

I ll think more but I can't say I understand it well enough

 

[Mark44]

Hmm what abou 141 ? the root is nearly 12 but the largest prime factor is 47 so how can we get it ?

3 divides 141, so 141/3 == 47

 

[Arman777]

hmm I see we have to also check that the result of the division also a prime or not.

 

[Mark44]

hmm I see we have to also check that the result of the division also a prime or not.

Yes, and that's what I said before.

 

[Arman777]

I have a good news and bad news good news is I write a code that calculates the largest prime factor for every odd N.

Sad thing is, the code gets awkward, when I put it our value (it makes infinite loop)..so we are near the end :)

#!/usr/bin/python
import math
N=64357
b=int(math.sqrt(N))
for h in range(3,b+1,2):
   if N%h == 0:
      l=N/h
      i=int(math.sqrt(l))
      for t in range (3,i+1,2):
         if l%t != 0:
            print(l)
         else:
            print(h)

Here the code

 

[Arman777]

Also, I noticed that it doesn't work for prime numbers so a great prime number calculator :) put a value and if its prime you 'll get nothing. The other thing that I noticed that for small N it prints one value but for larger N it starts to repeat itself many times.

 

[Vanadium 50]

Your refusal to write pseudocode is a mistake. Just sayin'.

 

[willem2]

Also, I noticed that it doesn't work for prime numbers so a great prime number calculator :) put a value and if its prime you 'll get nothing. The other thing that I noticed that for small N it prints one value but for larger N it starts to repeat itself many times.

You don't take into account that there may be more than 2 prime factors. The way you do it, you should have an infinite number of nested for loops.
It's really possible to merge all these for loops, and end up with a short program that will solve the problem in less than a second.

Once you've found a divisor, you can adjust N and a variable where you stored the square root of N (which is used to find the maximum divisor you have to test)
Since messing with the bounds of a for loop, or a range object is BAD, you should replace the for with a while.
Using more meaningful variable names is also good. You seem to use different letters every time.

N = 600851475143
divisor = 2
rootN = int(math.sqrt(N))
while (divisor <= rootN):
    if  N % divisor == 0:
        ....

This will be a lot more readable.
If you want to be really nitpicky, you should account for numbers that can be divided by the same prime factor more than once, altough the euler problem doesn't have this.

If this really doesn't work out, a recursive function might be easier. It;s likely to be useful for other euler problems as well:

we want a function factor that takes an integer>0 and produces a list of factors.
if n = 1 factor(n) is an empty list
if n > 1 you find the lowest prime factor of n which you call divisor and you return the factors produced by factor(n/divisor) and add divisor to this list.
---- if you can't find a divisor, the number is prime and you should return a list with only this number in it.

def factor(N):
    if N == 1: return []
    if N>1:
         # TODO: find lowest prime factor of N and put in divisor
         return [divisor] + factor(N//divisor)
        # TODO: if you didn't find a divisor

print(factor(600851475143))