Why loop doesn't work

Python Help
1

I am a beginner to python. I would like to write a program to find the first till 10th prime number.

Below is my code. For some reason the loop part in the function find_10th_prime doesn’t work. If I type find_10th_prime(100), the output is [2,1]. So the loop stops after the 1st prime is found.

def prime_check(primeNum,testNum):

      if len(primeNum)==0:
        return True
      elif len(primeNum) ==1 and testNum % primeNum[0] !=0:
        return True
      elif testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0:
        prime_check(primeNum[1:-1],testNum)
      else: return False

def find_10th_prime(max):
  counter=0
  primeNum=[2]
  for testNum in range(1,max+1):
    if counter>=10:
      print (counter)
      break
    elif prime_check (primeNum,testNum) == True:
      counter=counter +1
      print ("prime found")
      primeNum.append(testNum)
      print (primeNum,counter)
2

The loop does not stop after the first prime is found. It runs through all numbers from 1 to 100, but only 1 is added to the list.

Consider this line:

What is the result of this elif for any given number when primeNum[-1] is 1?

3

If “elif testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0:” is true, it will take out the first number and the last number from the prime number list and run the prime_check function based on the new prime number list.

I have test as below. The result is correct.
prime_check([1,2,3,5],11)

4

Try it with [2, 3, 5, 1]. Still correct?

Hint: 1 isn’t a prime number.

6

sorry, it looks there is also a problem with the prime_check function.
I have corrected the elseif condition as below:

def prime_check(primeNum,testNum):

  if len(primeNum)==0:
    return True
  elif len(primeNum) ==1 and testNum % primeNum[0] !=0:
    return True
  else: return testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0 and prime_check(primeNum[1:-1],testNum)
    #divide test number by first prime number and the last prime number, if both yield a remainder, continue the prime check 
    #by creating a new prime list (excl. the first prime and last prime from the prime list) & run the prime_check function again
    #based on the new prime list

However, I still don’t understand why this code doesn’t work.
elif testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0:
prime_check(primeNum[1:-1],testNum)

Blockquote

7

Using prime_check([2, 7], 9) as a starting point, the program flow will be thus:

elif testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0:  # 9 % 2 != 0 and 9 % 7 != 0; True.
    prime_check(primeNum[1:-1],testNum)

Here, prime_check is called again with arguments [7], 9. Let’s see what happens:

elif len(primeNum) ==1 and testNum % primeNum[0] !=0:  # len([7]) == 1 and 9 % 7 != 0; True.
    return True

This time the previous elif runs instead, returning True. However:

# Stepping back out:
elif testNum % primeNum[0] != 0 and testNum % primeNum[-1] != 0:
    prime_check(primeNum[1:-1],testNum)

The recursive prime_check call returns True, but you don’t do anything with it. The function finishes without reaching an explicit return statement, so the final return value is None.

Makes sense?

8

I think you should throw out this code and start again with a better algorithm for checking for prime numbers.

And better names for your variables would also help. Why do you have a list of primes called “primeNum” as if it was a single prime number?

There is no good reason to use recursion here (except maybe to prove it can be done, or to deliberately write an inefficient, obfuscated version). Recursion is a very unnatural way to do prime detection, especially since you are making multiple copies of the “primeNum” list of primes. You only need one copy of it.

primes = [2]  # Initial list of primes.

def is_prime(num):
    """Return True if num is prime."""
    for p in primes:
        if num % p == 0:
            return False
    return True

def find_10th_prime():
    # Skip 1, which we know is not a prime, 
    # and 2, which we know is.
    candidate = 3
    while len(primes) < 10:
        if is_prime(candidate):
            print(candidate, "is prime")
            primes.append(candidate)
        else:
            print(candidate, "is not prime")
        candidate += 1
    assert len(primes) == 10
    print("The tenth prime is", primes[-1])

If you think about which candidates are tested, you should realise that this does twice as much work as needed. You can halve the amount of candidates tested with a simple, one line change. Can you find it?

9

You are right! I assume it’s stupid mistake for veterans. the prime_check function simply runs the loop, but no input is stored for the caller as no return expression is used in the prime-check function

Thanks a lot for help!