Project Euler #3 with Python (Followup)

Question

I'm working on problem #3 on project euler, and I've run into a problem. It seems that the program is copying all the items from factors into prime_factors, instead of just the prime numbers. I assume this is because my is_prime function is not working properly. How can I make the function do what I want? Also, in the code, there is a line that I commented out. Do I need that line, or is it unnecessary? Finally, is the code as a whole sound (other than is_prime), or is it faulty?

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

A link to a previous question of mine on the same topic: https://stackoverflow.com/questions/24462105/project-euler-3-python?noredirect=1#comment37857323_24462105

thanks

import math
factors = []
prime_factors = []
def is_prime (x):
    counter = 0
    if x == 1:
        return False
    elif x == 2:
        return True
    for item in range (2, int(x)):
        if int(x) % item == 0:
            return False
        else:
            return True
number = int(input("Enter a number: "))
start = int(math.sqrt(number))
for item in range(2, start + 1):
    if number % item == 0:
        factors.append(item)
        #factors.append(number/item)   do i need this line?
for item in factors:
    if is_prime(item) == True:
        prime_factors.append(item)
print(prime_factors)

You don't know if you need this line! Did you write this code yourself or not? — emnoor, Jun 28 '14 at 17:00
@emnoor I did write the code myself, but I am not sure if that line is necessary or not. I wrote the code based off of an article describing how to find the prime factors of a large number (it was not specific to project euler). Also, I am a beginner, just having finished the Code Academy course. So I apologize for appearing ignorant or whatever. — leeamsi97, Jun 28 '14 at 17:49

score 2 · Answer 1 · answered Sep 16 '17 at 21:45

Yes, you need the commented line.

(It seems that on that case it's not necessary, but with other numbers the part of your code for getting factors would go wrong).

Check these references:

Prime numbers

Integer factorization

Why do we check up to the square root of a prime number to determine if it is prime or not

I got a very fast result on my computer with the following code:

#!/usr/bin/env python
import math

def square_root_as_int(x):
  return int(math.sqrt(x))

def is_prime(number):
  if number == 1:
    return False
  for x in range(2, square_root_as_int(number) + 1):
    if x == number:
      next
    if number % x == 0:
      return False
  return True

def factors_of_(number):
  factors = []
  for x in range(2, square_root_as_int(number) + 1):
    if number % x == 0:
      factors.append(x)
      factors.append(number/x)
  return factors

factors = factors_of_(600851475143)
primes = []
for factor in factors:
  if is_prime(factor):
    primes.append(factor)
print max(primes)

# Bonus: "functional way"
print max(filter(lambda x: is_prime(x), factors_of_(600851475143)))

score 1 · Answer 2 · answered Jun 28 '14 at 16:48

1

Your is_prime() returns early. Here's a fixed version:

def is_prime (x):
    if x == 1:
        return False
    if x == 2:
        return True
    for item in range (2, int(x)):
        if int(x) % item == 0:
            return False
    return True

answered Jun 28 '14 at 16:48

Bill Lynch

80,138
16
128
173

Thanks for your reply. could you clarify what significance your changes have? I notice that you changed the `elif` to an `if` and you put `return True` outside the `for` loop (as opposed to inside the `else` statement inside the `for` loop. – leeamsi97 Jun 28 '14 at 17:52
1

@leeamsi97 Take a pen and paper and try to go through your code execution manually for a number say 7. You will see the difference. – Aseem Bansal Jun 28 '14 at 18:09
@leeamsi97: The `elif` to an `if` is simply for cleaner code and does not change the output. Pulling the second `return` out of the `for` loop is the change that makes the difference. – Bill Lynch Jun 28 '14 at 20:21

score 1 · Answer 3 · answered Jun 28 '14 at 17:54

you should not be using int(x) in the way that you currently are. i know you're forcing the int type because you want to convert from string input, but this will also allow the user to enter a float (decimal), and have it interpreted as either prime or not. that is bad behavior for the function. see my solution below. if you use eval to verify the input, you can just use x later, in place of int(x).

import math
factors = []
prime_factors = []
def is_prime (x):
    x = eval(x) # this will cause a string like '5' to be evaluated as an integer. 
                # '5.2' will be evaluated as a float, on the other hand.
    if type(x) != int: 
         raise Exception('Please enter an integer.') #prevents bad input
    counter = 0 #this counter is not used. why is it initialized here?
    if x == 1:
        return False
    elif x == 2: 
        return True
    for item in range (2, x): 
        if x % item == 0:
            return False
        else:
            return True

score 0 · Answer 4 · answered Dec 18 '16 at 01:36

0

Use the while loop. n%i simply means n%i!=0

i = 2
n = 600851475143
while i*i <= n:
   if n%i:
          i+=1
   else:
          n //= i

print n

answered Dec 18 '16 at 01:36

Nipuna Upeksha

348
3
15

Project Euler #3 with Python (Followup)

4 Answers4