Python Beginner's Loop (Finding Primes)

Question

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/tutorial) I'm not unable to totally grasp how loops work. I've written some simple programs so I think I get the basics but for whatever reason this program that is meant to list all primes less than or equal to n is not working:

n = int(raw_input("What number should I go up to? "))
p = 2
while p <= n:
        for i in range(2, p):
                if p%i == 0:
                        p=p+1 
        print "%s" % p,
        p=p+1
print "Done"

The output when I enter 100 for example is:

2 3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87 89 95 97 101 Done

Which looks almost right but for some reason contains 27, 35, 95, which are composite of course. I've been trying to pick apart the way my loop works but I just don't see where it skips checking for divisibility suddenly. I figured that if someone had a look they could explain to me what about the syntax is causing this. Thanks a bunch!

Answer 1

My fast implementation returning the first 25 primes:

#!/usr/bin/env python3

from math import sqrt

def _is_prime(_num: int = None):
    if _num < 2:
        return False
    if _num > 3 and not (_num % 2 and _num % 3):
        return False
    return not any(_num % _ == 0 for _ in range(3, int(sqrt(_num) + 1), 2))

_cnt = 0
for _ in range(1, 1000):
        if _is_prime(_):
        _cnt += 1
        print(f"Prime N°: {_:,} | Count: {_cnt:,}")

Answer 2

Here's a more extensive example with optimization in mind for Python 3.

import sys

inner_loop_iterations: int = 0

def is_prime(n):
    a: int = 2
    global inner_loop_iterations

    if n == 1:
        return("Not prime")
    elif n == 2:
        return("Prime")

    while a * a <= n + 1:
        inner_loop_iterations += 1
        # This if statement reduces the number of inner loop iterations by roughy 50%
        # just weeding out the even numbers.
        if a % 2 == 0:
            a += 1
        else:
            a += 2

        if n % 2 == 0 or n % a == 0:
            return ("Not prime")
    else:
        return ("Prime")

while True:
    sys.stdout.write("Enter number to see if it's prime ('q' to quit): ")
    n = input()
    if not n:
        continue
    if n == 'q':
        break

    try:
        n = int(n)
    except ValueError:
        print("Please enter a valid number")

    if n < 1:
        print("Please enter a valid number")
        continue

    sys.stdout.write("{}\n".format(is_prime(n)))
    sys.stderr.write("Inner loops: {}\n\n".format(inner_loop_iterations))
    inner_loop_iterations=0

This program has two main optimizations, first it only iterates from 2 to the square root of n and it only iterates through odd numbers. Using these optimizations I was able to find out that the number 1000000007 is prime in only 15811 loop iterations.

Answer 3

def findprime(num):
  count = 0
  for i in range(1,num+1):
    list1 = []
    for ch in range(1,i+1):
      if i%1==0 and i%ch==0:
        list1.append(ch)
    if len(list1)==2:
      count += 1
      print(i,end=", ")
  print()
  return count  
num2 = int(input("enter a number: "))
result=findprime(num2)
print("prime numbers between 1 and",num2,"are",result)

Answer 4

for i in range(2, p):
    if p%i == 0:
        p=p+1 
     print "%s" % p,
     p=p+1

I am going to tell your error only,in line 3 you are incrimenting p but actually what you are missing is your i if your i in previous case is let say 13 then it will check your loop after 13 but it is leaving 2,3,5,7,11 so its an error .that is what happening in case of 27 your i before 27 is 13 and now it will check from 14.and I don't think u need an solution.

Answer 5

print('Enter a Number: ')
number=abs(int(input()))
my_List=[0,1]
def is_prime(n):
    if n in my_List:
        return True
    elif n>=2:
        for i in range(2, n):
            if n%i == 0:
                return False
        return True
    else:
        return False

if is_prime(number):
    print("%d is Prime!"%number)
else:
    print(number,'is not prime')

Answer 6

This in my opinion is a more optimised way. This finds all the prime numbers up to 1,000,000 in less than 8 seconds on my setup.

It is also one of my very first attempts at python, so I stand to be corrected

class prime:
    def finder (self):
        import math
        n = long(raw_input("What number should I go up to? "))
        for i in range(2, n):
            is_prime = True
            if i % 2 == 0:
                is_prime = False
            for j in range(3, long(math.sqrt(i) + 1), 2):
                if i % j == 0:
                    is_prime = False
                    break
            if is_prime:
                print(i)


prime().finder()

Answer 7

Let's do a couple more improvements.

1. You know 2 is the only even prime number, so you add 2 in your list and start from 3 incrementing your number to be checked by 2.
2. Once you are past the half-way point (see above sqrt and * examples), you don't need to test for a prime number.
3. If you use a list to keep track of the prime numbers, all you need to do is to divide by those prime numbers.

I wrote my code and each of the above items would improve my code execution time by about 500%.

prime_list=[2]
def is_prime(a_num):
    for i in prime_list:
        div, rem = divmod(a_num, i)
        if rem == 0:
            return False    
        elif div < i:
            break;

    prime_list.append(a_num)        
    return True    

Answer 8

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

To find PRIME NUMBER

Answer 9

This should work and is bit more optimized

import math
for i in range(2, 99):
  is_prime = True
  for j in range(2, int(math.sqrt(i)+1)):
    if i % j == 0:
      is_prime = False
  if is_prime:
    print(i)

Answer 10

Better use

for i in range(2, p//2 + 1):

Answer 11

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

p = i = 2
while p <= n:
    i = 2
    while i < p:
        if p%i == 0:
            p += 1 
            i = 1
        i += 1

    print p,
    p += 1

print "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.

Answer 12

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.

def is_prime(n):
    i = 2
    while i < n:
        if n%i == 0:
            return False
        i += 1
    return True


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

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

print "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:

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


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

for p in range(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():

def is_prime(n):
    return not any(n%i == 0 for i in range(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.

Answer 13

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:
            break
    else:
        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.

Answer 14

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 = 2
while p <= n:
    is_prime=True
    for i in range(2, p):
        if p%i == 0:
            is_prime=False
            break;
    if is_prime==True:
        print "%d is a Prime Number\n" % p
    p=p+1