6/15 - is_prime


#1

My code:

def is_prime(x):
  for n in range(2,x - 1):
    if x % n == 0:
      return False
    else:
      return True

Error at the bottom of the screen:
image
I don’t know what it’s trying to tell me except that I’m not there yet.

I looked at the solution, expecting to see that I was very close–maybe that I had formatted my range() incorrectly or something–but found that the entire structure of the solution was different. I didn’t let myself look at it for long because I didn’t want to retain the answer… but now I have no idea how to begin.

If I had to reinvent the wheel and create a process for finding prime numbers out of thin air, I’d iterate through every number in sequence from 2 to some designated stopping point (z I guess), test each one to see if it was divisible by 2, 3, 4, 5, 6, 7, 8, or 9, and return True or False depending on what the number was and what its divisors were. However, I don’t know how to translate that process into code.

I’m confident I’ll need a for-loop but that’s about as far as I’ve gotten. I thought I had done it, but it appears I have not.


#2

How many iterations does your loop do when x is 0?
How many iterations does your loop do when the function exits each iteration?


#3

Thank you, that gives me some direction.


#4

Just print out every single decision being made.

Print out the numbers you’re looping through. Print out the remainder.


#5

First, I didn’t include the instructions last time, so here they are:

Here’s what I have now:

def is_prime(x, z):
  while x > 0 and x < z:
    for n in range(2,x - 1):
      if x % n == 0:
        return False
      else:
        return True
    else:
      break
print is_prime(1, 92348238)

I added a while statement but I didn’t know how to terminate it without adding a second input in the beginning of the program to prevent infinity. While this is the first time the program has actually run without a hard error, it is clear I have failed the exercise:
image

It is also clear my code is bad because in a range from one to more than ninety-two million, the console tells me there are no prime numbers.

I also didn’t understand your advice to print everything that happens. The only opportunity I have to print anything is to run the entire code as a whole–which I tried to do, but it just tells me None.


#6

You can solve this either with a single while loop, or a single for loop. You certainly don’t need both.

Having read several of your threads, I think a common source of confusion for you with these exercises is that you’re diving in and attempting to write code to solve the problem without fully understanding what the problem is or what the process you need to follow to get the result should be.

Perhaps it would help you to take a step back from the code, and consider how you would solve the problem if you had to do the math by hand with a pencil and paper. If you can’t write out a step-by-step of how you’d do this manually, with every decision you’d make to determine if a given number is prime, then you’re going to struggle to create a program that does the job.

Yes, your code in this instance is definitely not great. I’m not sure if you’re just racing through the content, but I don’t think you’re taking the time to make sure you understand the topics of each lesson before progressing along to the next. By your own admission, you’re not 100% on using the while loop here so I have to wonder whether there’s other things in your code that you’re not completely sure of but are simply rolling with because you’ve managed to get it to work.

What @ionatan means (I presume) is that you ought to add print statements inside your function, which will allow you to follow in the console how Python is stepping through your program and see exactly what it’s doing.

I’ve taken the liberty of modifying your code as ionatan suggested, and included some print statements so we can follow the process Python takes when running it. Here’s my amended code:

def is_prime(x, z):
  print "Entering the while loop"
  while x > 0 and x < z:
    print "Inside the while loop"
    print "Entering the for loop"
    for n in range(2,x - 1):
      print "Inside the for loop"
      if x % n == 0:
        print "%d divided by %d returns %d. Not prime." % (x, n, (x%n))
        return False
      else:
        print "%d divided by %d returns %d. Possibly prime?" % (x, n, (x%n))
        return True
    else:
      print "Inside the for ELSE block!"
      break

If we run your code, by calling print is_prime(1, 92348238) we get the following back from Python:

Entering the while loop
Inside the while loop
Entering the for loop
Inside the for ELSE block!
None

Now we know the route that Python is taking through your program, we can look at why it doesn’t work as intended.

We can see that Python gets to the point of beginning the for loop without a problem, so programmatically there’s nothing wrong with your code up to the line for n in range(2,x - 1):

Notice that Python never enters your for loop as we don’t see the output Inside the for loop in the console; instead, we see that Python has progressed into the else clause that trails your for loop. Once it’s here, it carries out your break statement which terminates the while loop, and that’s the final line of your function.

You might be asking why we see None as the final output to the console.

We’ve told Python to print the output of your is_prime function by using print is_prime(1, 92348238). We’re expecting some output from your function, since we’re trying to print it, but the way you tell the function what the output should be is with the return statement. None of the return statements in your code ever get executed, so instead Python gives you a default output in the form of None. This is not your program telling you there were no prime numbers between 1 and 92348238. :slight_smile:

So, finally, why does Python never enter your for loop?

The for statement iterates over the elements of a sequence, such as a tuple or a list. When Python reaches your for statement, it evaluates the iterable object to create the sequence it must loop through. In your code, you’re telling Python to iterate through range(2, x - 1). Python needs to evaluate that and create an iterable sequence before it can carry on.

Your problem is that, if we call your function by using is_prime(1, 92348238) then x = 1. In turn, this means our range becomes range(2, 0). This is invalid, and we can see why if we just print that range to the console:

>>> print range(2,0)
[]
>>>

The reason this doesn’t work is because in the range function, we can provide three parameters: start, stop, and step like so: range(start,stop,step).

If you don’t specify the value for step, it defaults to 1. We can’t start at 2 and add any amount of 1s to reach 0, so the output is an empty list.

The default behaviour for for when presented with an empty list is to proceed to the else statement, if there is one. This is the behaviour we see in your program.

(Your code also won’t work even if we provided a larger value for x, say 7. I won’t go into the why of that in this post… it’s long enough already!)

Sorry for the epic long post, but hopefully this’ll help you see where you’ve gone wrong. :slight_smile: I would again strongly encourage you to think about the manual process you’d follow to check whether a number is prime, and then once you’re sure that’s right try and implement it in Python.

:slight_smile:


#7

Thank you for this. I really appreciate the insight. You’re definitely right about my not understanding the lay of the land before I dig in and start tunneling. I looked at my notes from this exercise and decided I should go back and review earlier stuff.

Everyone has been really helpful at pointing me in the right direction without giving away the solutions, but no amount of guidance can overcome not knowing the requisite stuff.

The epicness came very welcome, I really appreciate all of this.


#8

Which begins with understanding the problem. It’s math. This seems to escape some folk’s attention.

It uses a well known math and algebra concept… factoring. How would we go about finding all the prime factors of a non-prime number?

Eg.

337500 => 2 ** 2 * 3 ** 3 * 5 ** 5 => 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5 * 5 * 5

What do we know about Prime numbers? For starters we know that every number can be expressed as the product of two or more primes (each to any degree 1..n) (citation missing). We know that primes are not divisible, except by unity, which is moot. The quotient equals the dividend.

When testing by division there is no else. Divisible? Outta here…

if x % n: continue
return False

More math… There is little point testing any values greater than half of a number. The whole group will not divide into x. The fixation that people have with x or x - 1 is absolutely pointlesss.

Test 19.

19 % 2  => 1
19 % 3  => 1
19 % 4  => 3
19 % 5  => 4
19 % 6  => 1
19 % 7  => 5
19 % 8  => 3
19 % 9  => 1

No point going any further. We know that 10 and above couldn’t possibly go into 19. Since all the above modulos were non-zero, we have a prime.

Going back to the original assertion that every non-prime is a product of primes, we can assert that the only factors we need to test against will be primes, notwithstanding that further examination reveals that the squate root is the largest factor with which we need to concern ourselves. It gives us an upper limit on the prime factors list.

Test 19.

19 % 2  => 1
19 % 3  => 1
19 % 4  => 3
19 % 5  => 4

End of story. It’s prime.

Note that if we were reading a memoized list of primes, 4 would not be in the list of test factors.


#9

On the one hand, jumping in and playing around with new stuff is a lot of the time a good way to learn. You build it, you break it, you learn how to fix it.

Where I think you’re possibly running into difficulty is you’re jumping in and playing around with multiple things at once, and then when they’re not working correctly you’re having trouble working out how each thing is breaking.

Going back over the earlier content is a good idea, for sure, but I’d definitely suggest that you spend some time just messing around with each thing on it’s own in isolation so you can work out how it does its thing.

(For example, you could just mess around with while loops - they don’t need to do anything complicated inside the loop, just throw a couple of print statements in so you can see it doing something. Then add the else clause to the while loop, and see how that affects program flow.)

No worries. Some of the other topics of yours that I’ve posted in, you’ve not been far off the solution. I think once you’ve spent a bit of time reviewing the previous material, and if you get into the habit of working out a non-code process for solving the problem before you try and code it, you’ll be better placed to solve the exercises on Codecademy. :slight_smile:

If you run into anything else that stumps you or you want more info on, there’s always the forum! :slight_smile:


#10

learn it or don’t use it
can’t use what you don’t know, no point trying, whatever trying means because you just can’t


#11

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.