Python Beginner's Loop (finding Primes)

I'm truly a beginner at python so I apologise for the lack of knowledge, but the reason I'm asking is that reading the Python manual and tutorial (http://docs.python.org/2.7/tutori

Solution 1:

I would actually restructure the program to look like this:

for p in range(2, n+1):
    for i in range(2, p):
        if p % i == 0:
            breakelse:
        print p,
print'Done'

This is perhaps a more idiomatic solution (using a for loop instead of a while loop), and works perfectly.

The outer for loop iterates through all the numbers from 2 to n.

The inner one iterates to all numbers from 2 to p. If it reaches a number that divides evenly into p, then it breaks out of the inner loop.

The else block executes every time the for loop isn't broken out of (printing the prime numbers).

Then the program prints 'Done' after it finishes.

As a side note, you only need to iterate through 2 to the square root of p, since each factor has a pair. If you don't get a match there won't be any other factors after the square root, and the number will be prime.

Solution 2:

Your code has two loops, one inside another. It should help you figure out the code if you replace the inner loop with a function. Then make sure the function is correct and can stand on its own (separate from the outer loop).

Here is my rewrite of your original code. This rewrite works perfectly.

defis_prime(n):
    i = 2while i < n:
        if n%i == 0:
            returnFalse
        i += 1returnTrue


n = int(raw_input("What number should I go up to? "))

p = 2while p <= n:
    if is_prime(p):
        print p,
    p=p+1print"Done"

Note that is_prime() doesn't touch the loop index of the outer loop. It is a stand-alone pure function. Incrementing p inside the inner loop was the problem, and this decomposed version doesn't have the problem.

Now we can easily rewrite using for loops and I think the code gets improved:

defis_prime(n):
    for i inrange(2, n):
        if n%i == 0:
            returnFalsereturnTrue


n = int(raw_input("What number should I go up to? "))

for p inrange(2, n+1):
    if is_prime(p):
        print p,

print"Done"

Note that in Python, range() never includes the upper bound that you pass in. So the inner loop, which checks for < n, we can simply call range(2, n) but for the outer loop, where we want <= n, we need to add one to n so that n will be included: range(2, n+1)

Python has some built-in stuff that is fun. You don't need to learn all these tricks right away, but here is another way you can write is_prime():

defis_prime(n):
    returnnotany(n%i == 0for i inrange(2, n))

This works just like the for loop version of is_prime(). It sets i to values from range(2, n) and checks each one, and if a test ever fails it stops checking and returns. If it checks n against every number in the range and not any of them divide n evenly, then the number is prime.

Again, you don't need to learn all these tricks right away, but I think they are kind of fun when you do learn them.

Solution 3:

This should work and is bit more optimized

import math
for i inrange(2, 99):
  is_prime = Truefor j inrange(2, int(math.sqrt(i)+1)):
    if i % j == 0:
      is_prime = Falseif is_prime:
    print(i)

Solution 4:

Please compare your snippet with the one pasted below and you will notice where you were wrong.

n = int(raw_input("What number should I go up to? "))
p = 2while p <= n:
    is_prime=Truefor i inrange(2, p):
        if p%i == 0:
            is_prime=Falsebreak;
    if is_prime==True:
        print"%d is a Prime Number\n" % p
    p=p+1

Solution 5:

you do not re-start the i loop after you find a non-prime

p = i = 2while p <= n:
    i = 2while i < p:
        if p%i == 0:
            p += 1 
            i = 1
        i += 1print p,
    p += 1print"Done"

A while loop executes the body, and then checks if the condition at the top is True, if it is true, it does the body again. A for loop executes the body once for each item in the iterator.