primes

[Mouche]

I know printing primes isn't anything new, but (like always) I'd love to hear some feedback on how I can make my code more efficient and other constructive criticism.

def print_primes(r=10):
    primes = [ ]
    for i in range(2,r+1):
        prime = 1
        for divisor in range(2,i):
            if i % divisor == 0:
                prime = 0
                break
        if prime:
            primes.append(i)
    print "primes between 1 and %d:" % (r)
    for prime in primes:
        print prime,

print_primes()

Thanks.

EDIT: BAH! I CAN'T DELETE THIS! I just realized there's another prime thread and it has more advanced versions of this program. Sorry for the nuisance!

[Matt Tacular]

You've probably seen the my thread. The things I've done to make mine the mastest, the biggest improvements were done by making the code not even bother to check to see if even numbers are prime numbers because we know they wont be. Do that by making the range of numbers to check go up by 2's, starting at 3 (it won't find 2, but it will find every other prime number). Also, why divide by even numbers if we're not checking even numbers, so make the division range also go up by two's starting at 3, and also, don't check to see if any number beyond half is divisible.

#Changed the range.
def print_primes(r=100):

    #The below change won't find 2 as a prime, by will find all others, so let's just add it ourselves.
    primes = [2]

    #Start at 3 and go up by 2's because we already know that every even number is not a prime
    for i in range(3,(r+1),2):
        prime = 1

        #Don't bother check numbers that are even.  And don't check beyond half.
        for divisor in range(3,(i//2),2):
            if i % divisor == 0:
                prime = 0
                break
        if prime:
            primes.append(i)
    print "primes between 1 and %d:" % (r)

    #if you want your code to perform faster, printing the list seems to go faster
    #with large amounts of primes instead of going through the list one by one.
    #So you could use this:
    #                 "print primes"
    for prime in primes:
        print prime,

print_primes()

[Mouche]

Oh, excellent. Thank you.

I ran across this one method where you have a list of divisors and you remove all of the multiples as you go through. For example, say you're doing 1-100. It adds '2' as prime then deletes all multiples of two. Then adds '3' as a prime then deletes all the mutiples of three. This works okay, but this way, you can't do, say, primes from 100-200... you have to start with 1. Perhaps you could have it do it for 1 to your top number (lik 200 in 100-200) and then remove all numbers under 100 from your "primes" list. Meh, then it's not really more efficient.

Thanks for the comments though.

[Matt Tacular]

So you'd like to do a range that doesn't start at 1?

I tinkered with it for a minute and came to this:

#Changed the range.
def print_primes(r3,r2,r):

    primes = []

    #Since the range might not start at two, we need an if statement to add it if the range does start at two
    if r3 <=2:
        primes.append(2)
    
    #Start at 3 and go up by 2's because we already know that every even number is not a prime
    for i in range(r2,(r+1),2):
        prime = 1

        #Don't bother check numbers that are even.  And don't check beyond half.
        for divisor in range(3,(i//2),2):
            if i % divisor == 0:
                prime = 0
                break
        if prime:
            primes.append(i)
    print "primes between %d and %d:" % (r3,r)

    #if you want your code to perform faster, printing the list seems to go faster
    #with large amounts of primes instead of going through the list one by one.
    #So you could use this:
    #                 "print primes"
    for prime in primes:
        print prime,

start_number = 100 #change this number to change starting point for range.

#This will make sure the starting number odd.
if start_number % 1 == 0:
    start_number2 = start_number + 1

end_number = 200 #The ending number, or r

print_primes(start_number, start_number2, end_number)

You can now check any range of numbers for primes and still use what I was saying.

But to remove all multiples of the numbers you check. I'm not sure how to do that (quickly), although it would make the code faster. Because if you check to see if 5 is divisible and its not, what's the point in checking 10 or 15 right?

[bumsfeld]

I know printing primes isn't anything new, but (like always) I'd love to hear some feedback on how I can make my code more efficient and other constructive criticism.

def print_primes(r=10):
    primes = [ ]
    for i in range(2,r+1):
        prime = 1
        for divisor in range(2,i):
            if i % divisor == 0:
                prime = 0
                break
        if prime:
            primes.append(i)
    print "primes between 1 and %d:" % (r)
    for prime in primes:
        print prime,

print_primes()

Thanks.

EDIT: BAH! I CAN'T DELETE THIS! I just realized there's another prime thread and it has more advanced versions of this program. Sorry for the nuisance!

LaMouche, I am glad you posted this typical beginner's example! I improved your code a little bit and also showed the timing needed to follow positive progress. If you are interested, then see my code snippet at:
http://www.daniweb.com/code/snippet641.html

Mat has done much of interesting things too in his thread.

[arsham]

myarray = [2,3]
          
def prime(x):
    for i in range(3, x,2): 
        if filter(lambda x: i % x, myarray) == myarray :
            myarray.append(i)

[vegaseat]

Nice, I would code it like that ...

def prime(x, myarray=[2,3]):
    for i in range(3, x, 2):
        if filter(lambda x: i % x, myarray) == myarray :
            myarray.append(i)
    return myarray
 
prime_list = prime(15000)
 
# check the first 10 primes
print prime_list[:10]
# check the last 10 primes
print prime_list[-10:]

This particular prime function has a certain elegance to it, but suffers from slow performance (prime(15000) takes about 5 seconds and is 1000 times slower than the standard sieve algorithm)

[arsham]

I was thinking of the smallest code
This must go to sqr(x) while checking for being divide by x
So in that situation , this would be faster

Looking forward to see better solution

Good job dudes
Arsham