find prime numbers in python

Question

I need to write a code that will find all prime numbers in a range of numbers and then list them in order saying which are prime and which are not, and also if they are not prime, show by what numbers they are divisible. It should look something like this:

>>> Prime(1,10)
1 is not a prime number 
2 is a prime number
3 is a prime number
4 is divisible by 2
5 is a prime number
6 is divisible by 2, 3
7 is a prime number
8 is divisible by 2, 4
9 is divisible by 3

so far I have this which will only identify what numbers are prime and print them in a list. I don't know how to do the non prime numbers and to print what numbers it is divisible by. Also I get that 1 is a prime number.

def primeNum(num1, num2):
   for num in range(num1,num2):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num,'is a prime number')

Answer 1

Using a sieve will do the trick:

Example:

from __future__ import print_function


def primes():
    """Prime Number Generator

    Generator an infinite sequence of primes

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    """

    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


def factors(n):
    yield 1
    i = 2
    limit = n**0.5
    while i <= limit:
        if n % i == 0:
            yield i
            n = n / i
            limit = n**0.5
        else:
            i += 1
    if n > 1:
        yield n


def primerange(start, stop):
    pg = primes()
    p = next(pg)

    for i in xrange(start, stop):
        while p < i:
            p = next(pg)

        if p == i:
            print("{0} is prime".format(i))
        else:
            print("{0} is not prime and has factors: {1}".format(i, ", ".join(map(str, set(factors(i))))))

Output:

>>> primerange(1, 10)
1 is not prime and has factors: 1
2 is prime
3 is prime
4 is not prime and has factors: 1, 2
5 is prime
6 is not prime and has factors: 1, 2, 3
7 is prime
8 is not prime and has factors: 1, 2
9 is not prime and has factors: 1, 3

Answer 2

Just add a print and a break at the position where you set prime to false.

A more elegant solution would be to make a separate function isPrime or to use break and else in the inner for loop. Either way would make prime unnecessary.

You can only divide one by one and itself so it is a prime number, by that definition at least.

Answer 3

you could store the divisors for each number on a list and then print it with ", ".join(yourList)

i.e:

def primeNum(num1, num2):
   for num in range(num1,num2):
       divisors = []
       for i in range(2,num):
           if (num%i == 0):
               divisors.append(str(i))
       if divisors:
           print ('%d is divisible by ' %num + ', '.join(divisors))
       else:
           print ('%d is a prime number' %num)

Edit: dumb syntax error