CODEWITHSUNDEEP
pythonmath
Chenxiong Yi
Chenxiong Yi

Reputation: 11

why can't I get a prime number using this python file?

I am a beginner of python, and I was doing a problem on project euler that asks me to find largest prime number. But my code did not work as I expected, and the number I got was not a prime number.Though working on this for a long time, I still could not find the problem. my code is 

def is_prime(x):
  for i in range(2,x):
    if x%i==0:
        return False
    else:
        return True
def largest_prime_factor(x):
  a=range(1,x)
  list1=[]
  for i in a:
    if x%i==0 and is_prime(i) == True:
        list1.append(i)
  print max(list1)

anybody here can tell me why my code is wrong ? thanks u in advance

Upvotes: 0

Views: 63

Answers (3)

Bakuriu
Bakuriu

Reputation: 101989

There are three errors in your code. One, was already pointed out: you should return True at the end of the loop in is_prime. An other one is that 1 is not prime:

def is_prime(x):
   if x == 1:
       # 1 is not prime!
       return False

   # you can loop up to ceil(sqrt(x)) instead of all the way up to x
   for i in range(2, int(x**.5) + 1):
      if x%i==0:
          return False
      elif i > x:
          break   
   return True

The other is that largest_prime_factor is raising an error for prime numbers:

In [7]: largest_prime_factor(7)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-7-eceaf4811bfe> in <module>()
----> 1 largest_prime_factor(7)

<ipython-input-6-d40692628493> in largest_prime_factor(x)
     12     if x%i==0 and is_prime(i):
     13         list1.append(i)
---> 14   return max(list1)

ValueError: max() arg is an empty sequence

(Or returns 1 if you use the incorrect version of is_prime that considers 1 a prime number)

The problem is that range(1, x) doesn't contain x. So the loop in largest_prime_factor, when x is prime, will not be able to add x as factor. You should loop over a range that contains x:

def largest_prime_factor(x):
    list1=[]
    for i in range(1, x+1):
       if x%i==0 and is_prime(i):
           list1.append(i)
    return max(list1)

However this is quite inefficient. Instead you could loop up to sqrt(x) as in is_prime, but when you find a factor you divide x:

from itertools import chain

def largest_prime_factor(x):
    factors = []
    for div in chain([2], range(3, int(x**.5) + 1, 2)):
        while x % div == 0:
            factors.append(div)
            x //= div
        if div > x:
            break
    if x != 1:
        # return x   # should be okay to do this because x was prime
        factors.append(x)
    return max(factors)

This is more efficient because it has to loop only up to sqrt(x), and returns the correct result:

In [11]: largest_prime_factor(7)
Out[11]: 7

Upvotes: 2

Joop Eggen
Joop Eggen

Reputation: 109597

In the loop one should only return false, return true when ALL steps where tried.

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

def largest_prime_factor(x):
  a=range(1,x)
  list1=[]
  for i in a:
    if is_prime(i):
        list1.append(i)
  print max(list1)

Upvotes: 0

Zhouster
Zhouster

Reputation: 746

The issue lies within your is_prime(x). It returns on the first instance of the function call. So instead of returning True or False, you might want to store it as a boolean or do some return logic. It could look something like this:

if x%i==0:
    continue
else:
    return False

Then return True at the end of the function if it reaches there.

Upvotes: 0

Related Questions