Stuck on Project Euler #3 in python

Question

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

Ok, so i am working on project euler problem 3 in python. I am kind of confused. I can't tell if the answers that i am getting with this program are correct or not. If somone could please tell me what im doing wrong it would be great!

#import pdb

odd_list=[]
prime_list=[2] #Begin with zero so that we can pop later without errors.

#Define a function that finds all the odd numbers in the range of a number
def oddNumbers(x):

  x+=1 #add one to the number because range does not include it
  for i in range(x):
     if i%2!=0: #If it cannot be evenly divided by two it is eliminated
        odd_list.append(i) #Add it too the list
    
  return odd_list 

def findPrimes(number_to_test, list_of_odd_numbers_in_tested_number): # Pass in the prime number to test
   for i in list_of_odd_numbers_in_tested_number:
     if number_to_test % i==0:
       prime_list.append(i)
       number_to_test=number_to_test / i
          
       #prime_list.append(i)
       #prime_list.pop(-2) #remove the old number so that we only have the biggest

       if prime_list==[1]:
           print "This has no prime factors other than 1"
       else:
           print prime_list
       return prime_list
        
    #pdb.set_trace()

    number_to_test=raw_input("What number would you like to find the greatest prime of?\n:")

    #Convert the input to an integer
    number_to_test=int(number_to_test)

    #Pass the number to the oddnumbers function
    odds=oddNumbers(number_to_test)

#Pass the return of the oddnumbers function to the findPrimes function
findPrimes(number_to_test , odds)        

Answer 1

The simple solution is trial division. Let's work through the factorization of 13195, then you can apply that method to the larger number that interests you.

Start with a trial divisor of 2; 13195 divided by 2 leaves a remainder of 1, so 2 does not divide 13195, and we can go on to the next trial divisor. Next we try 3, but that leaves a remainder of 1; then we try 4, but that leaves a remainder of 3. The next trial divisor is 5, and that does divide 13195, so we output 5 as a factor of 13195, reduce the original number to 2639 = 13195 / 5, and try 5 again. Now 2639 divided by 5 leaves a remainder of 4, so we advance to 6, which leaves a remainder of 5, then we advance to 7, which does divide 2639, so we output 7 as a factor of 2639 (and also a factor of 13195) and reduce the original number again to 377 = 2639 / 7. Now we try 7 again, but it fails to divide 377, as does 8, and 9, and 10, and 11, and 12, but 13 divides 2639. So we output 13 as a divisor of 377 (and of 2639 and 13195) and reduce the original number again to 29 = 377 / 13. As this point we are finished, because the square of the trial divisor, which is still 13, is greater than the remaining number, 29, which proves that 29 is prime; that is so because if n=pq, then either p or q must be less than, or equal to the square root of n, and since we have tried all those divisors, the remaining number, 29, must be prime. Thus, 13195 = 5 * 7 * 13 * 29.

Here's a pseudocode description of the algorithm:

function factors(n)
    f = 2
    while f * f <= n
        if f divides n
            output f
            n = n / f
        else
            f = f + 1
    output n

There are better ways to factor integers. But this method is sufficient for Project Euler #3, and for many other factorization projects as well. If you want to learn more about prime numbers and factorization, I modestly recommend the essay Programming with Prime Numbers at my blog, which among other things has a python implementation of the algorithm described above.

Answer 2

• the number 600851475143 is big to discourage you to use brute-force.
• the oddNumbers function in going to put 600851475143 / 2 numbers in odd_list, that's a lot of memory.
• checking that a number can be divided by an odd number does not mean the odd number is a prime number. the algorithm you provided is wrong.
• there are a lot of mathematical/algorithm tricks about prime numbers, you should and search them online then sieve through the answers. you might also get to the root of the problem to make sure you have squared away some of the issues.

you could use a generator to get the list of odds (not that it will help you):

odd_list = xrange(1, number+1, 2)

here are the concepts needed to deal with prime numbers:

• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• http://en.wikipedia.org/wiki/Primality_test

if you are really stuck, then there are solutions already there:

• Project Euler #3, infinite loop on factorization
• Project Euler 3 - Why does this method work?
• Project Euler Question 3 Help

Answer 3

Here is my Python code:

num=600851475143
i=2 # Smallest prime factor
for k in range(0,num):
    if i >= num: # Prime factor of the number should not be greater than the number
        break
    elif num % i == 0: # Check if the number is evenly divisible by i
        num = num / i
    else:
        i= i + 1
print ("biggest prime number is: "+str(num))   

Answer 4

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

What is the largest prime factor of the number 600851475143 ?
'''
import math

def isPrime(x):
    if x<2:
        return False
    for i in range(2,int(math.sqrt(x))):
        if not x%i:
           return False
    return True

def largest_factor(number):
    for i in range (2, int(math.sqrt(number))):
        if number%i == 0:
            number = number/i
            if isPrime(number) is True:
                max_val = number
                break
                print max_val
        else:
            i += 1
    return max_val

largest_factor(600851475143)

This actually compiles very fast. It checks for the number formed for being the prime number or not. Thanks

Answer 5

Another solution to this problem using Python.

def lpf(x):
lpf=2
while (x>lpf):
    if (x%lpf==0):
        x=x/lpf

    else:
        lpf+=1
return x
print(lpf(600851475143))

Answer 6

i = 3
factor = []
number = 600851475143
while i * i <= number:
    if number % i != 0:
        i += 2
    else:
        number /= i
        factor.append(i)
while number >= i:
    if number % i != 0:
        i += 2
    else:
        number /= i
        factor.append(i)
print(max(factor))

Answer 7

Here is my python code

a=2
list1=[]
while a<=13195:                     #replace 13195 with your input number
    if 13195 %a ==0:                #replace 13195 with your input number
        x , count = 2, 0
        while x <=a:
            if a%x ==0:
                count+=1
            x+=1
        if count <2:
            list1.append(a)
    a+=1

print (max(list1))

Answer 8

Here is my python code:

import math
ma = 600851475143
mn = 2
s = []
while mn < math.sqrt(ma):
    rez = ma / mn
    mn += 1
    if ma % mn == 0:
        s.append(mn)
print(max(s))

Answer 9

def prime_max(x):
a = x
i = 2
while i in range(2,int(a+1)):
    if a%i == 0:
        a = a/i
        
        if a == 1:
             print(i)
        i = i-1
    i = i+1