My prime Number generator

[Matt Tacular]

Can someone look at this and tell me if it actually is doing what it's supposed to.

from __future__ import division

counter = 1       

while True:
    li = []
    for i in range(1,(counter+1)):
        if (counter/i) % 1 == 0:
            li.append(i)
    if len(li) <= 2:
        print counter,"is a prime."
    counter = counter + 1

It starts from 1 and goes on forever, and for every one of those numbers it divides by every number between 1 and that number. If the resulting number is a whole number it adds it to the list. At the end, it sees if the list only contains two, or less, numbers, if it does, then its a prime number (1 and the number itself should divide).

Thanks

[Matt Tacular]

change

"if len(li) <= 2:" to "if len(li) == 2:"

Because apparently if you look up on wikipedia, 1 is not a prime, I did not know that.

[jrcagle]

Cool program!

The inner for loop can test up to math.sqrt(counter) (== counter**(0.5)), because any factor f of counter has to be paired with counter/f, and either f or counter/f is guaranteed to be <= sqrt(counter). That can save you some time.

Also, the Sieve of Eristothanes is worth checking out both for math's sake and also for faster code's sake.

Regards,
Jeff

[Matt Tacular]

I was thinking of making it quit the loop as soon as it found a factor that isn't one or the counter.

[Matt Tacular]

I optimized it a bit, and timed the two of them, the first one took 20 seconds (give or take) to get to the prime numbers in the 10 000 range, while this new one takes 3, give or take. If I may say so I think it's a vast improvement.

from __future__ import division

counter = 2       

while True:
    prime = True
    for i in range(2,(counter)):
        if (counter/i) % 1 == 0:
            prime = False
            break
    if prime == True:
        print counter,"is a prime."
    counter = counter + 1

I'm sure I could make it faster, for example, don't even bother check numbers that end with 0,2,4,6, or 8.

[sneekula]

I think your print to the display will be by far the slowest operation.

[a1eio]

yea, ditch the printing and append it to a list and it'll be almost instant. :)

[bumsfeld]

yea, ditch the printing and append it to a list and it'll be almost instant. :)

Even with ditching print and returning list of primes, this algorithm is not like speed demon. It takes 6,000ms for primes up to 10,000 compared to 4ms with standard sieve algorithm.

[Matt Tacular]

Well I'm not a pro with python, and this wasn't intended to be a quick thing at all, I started this with the train of thought: "I wonder if I could make a program that finds prime numbers."

I did, but then I tweaked it a tad. If I wanted to make it faster, it wouldn't check numbers at all that are divisible by 2 or any already found prime. Other than that I wouldn't know what to do with it.

But wouldn't you guys be impressed if I, a novice at python, were able of making a python script as fast or faster than the sieve thingy?

Admit it, you would all be amazed.

[jrcagle]

But wouldn't you guys be impressed if I, a novice at python, were able of making a python script as fast or faster than the sieve thingy?

Admit it, you would all be amazed.

Indeed we would. And the fellows from Fort Meade (NSA) would come knocking at your door, too. Something like a guaranteed job ... :)

Seriously, the program is good; the sieve recommendation is just for "further study."

Jeff

[Matt Tacular]

I did improve upon it some more. I thought to myself: "what's the point in dividing by ALL the numbers between 0 and one lower than the number?", and then "why not just half way?" also, I got rid of the printing to screen and appended it to a list, so it seems very quick.

from __future__ import division

def main():
    num = input("How high to find prime numbers? ")
    li = [2]
    for i2 in range(3,(num+1),2):
        prime = True
        for i in range(2,(i2/2)):
            if (i2/i) % 1 == 0:
                prime = False
                break
        if prime == True:
            li.append(i2)
    print li

main()

while True:
    go_again = raw_input("Again?(y/n) ")
    if go_again.lower()[0] == "y":
        main()
    else:
        break

[vegaseat]

With from __future__ import division I can see a problem in line for i in range(2,(i2/2)): you get a float from the division and range does not like floats. Change this line to for i in range(2,(i2//2)):

Nice thinking here, have to see what Bumsfeld's timing comes up with.

[Matt Tacular]

Thanks vegaseat

but what does that do?

[edit]just thought I would point something else out in my code, the first range is like that because what's the point in checking numbers we know to be divisible by 2? And since I did that I just threw 2 into the list already because it wouldn't find two like that.

[vegaseat]

When you use 'from __future__ import division' then the '/' operator will do floating point division. Python actually has a '//' operator for integer division (floor or quotient) that was seldomly used, since '/' did the same thing. With new versions of Python the '//' will become more popular, since integer divisions are still needed.

[jrcagle]

With new versions of Python the '//' will become more popular, since integer divisions are still needed.

... and old code will break frequently, since division will no longer yield integers. :eek:

Jeff

[Matt Tacular]

I sped it up again, "if I'm not even bothering to check even numbers, why divide by 2,4,6,etc.?"

replace:

for i in range(2,(i2//2)):

With

for i in range(3,(i2//2),2):

[vegaseat]

I sped it up again, "if I'm not even bothering to check even numbers, why divide by 2,4,6,etc.?"

replace:

for i in range(2,(i2//2)):

With

for i in range(3,(i2//2),2):

Great thinking! I tested it out with 10,000 primes. That made it about 4 times faster than the previous code.

[Ene Uran]

... and old code will break frequently, since division will no longer yield integers. :eek:

Jeff

This is why it hasn't been implemented yet in a large number of other languages like C, C++ either.

[Matt Tacular]

Another tweak.

With the part of the code that does the dividing: I thought that going half way would be the fastest because what's the point in going the whole way right? After all nothing is going to be divisible past the half way point, take for example 100, nothing past 50 will be divisible, it's just plain imposible. But I was wrong, not with that whole statement, but when I thought that would be the fastest.

Another thing seems to be true, if nothing past the third is divisible, than nothing at all will be divisible either, take 15 for example, 5 and 10 are both divisible, but 10 is divisible by 5 and 5 is at the one third mark. So if we only checked up to 1 third, than 5 will be checked and there would be no need to check up to 10.

At first I thought this would work with a quarter, but numbers like 15 and 9 wouldn't be found out to not be a prime. I'm not 100% sure this works, but it seems to, if anyone notices any flaws let me know, thanks.

Heres the code:
Replace:

for i in range(3,(i2//2),2):

With

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

[Matt Tacular]

Actually going only a quarter the way through the numbers to divide does work, the only number it won't eliminate is 9. just like how I just added 2 to the list because the loop won't determine it a prime, just add a line to remove 9.

Here is my updated prime number generater. Still no where nearly as fast as the sieve thingy, but way faster than my original thing.

from __future__ import division

def main():
    num = input("How high to find prime numbers? ")
    li = [2]
    for i2 in range(3,(num+1),2):
        prime = True
        for i in range(3,((i2//4)+1),2):
            if (i2/i) % 1 == 0:
                prime = False
                break
        if prime == True:
            li.append(i2)
    li.remove(9)
    print li
    
main()

while True:
    go_again = raw_input("Again?(y/n) ")
    if go_again.lower()[0] == "y":
        main()
    else:
        break

[vegaseat]

You can also tweak a little more speed by using xrange() instead of range(). Your major problem now is the many time-costly function calls to appen() and range() within the loops. The highspeed prime number algorithms have all resorted to avoiding function calls within a loop and are using slicing instead.

[Matt Tacular]

What's slicing

Also, what's the difference between xrange and range?

[bumsfeld]

... and old code will break frequently, since division will no longer yield integers. :eek:

Jeff

Pascal always had two different divisors, one for integers and one for floats. So I was used to using '//' when I wanted integer division. Lucky me!? In C this problem comes up with beginners a lot.

[jrcagle]

range() generates the entire list at the first call. Thus,

for x in range(6):
   print x

does this:

(1) create the list [0,1,2,3,4,5]
(2) set x to the first element, 0
(3) print x
(4) set x to next element until no more elements, go back to (3).

xrange(), by contrast, creates a 'generator' that supplies the next element on demand. Thus,

for x in xrange(6):
   print x

does this:

(1) create a generator with start 0, end 5, add 1 for next element
(2) request next element from generator; if end, quit; else, set x to returned value.
(3) print x, goto (2)

Under a wide variety of circumstances, xrange() is the faster tool because the numbers are only generated as needed instead of all at once. So for example, if I want to test the primality of 10,000 and I compare these two snippets

for i in range(2, 10000/2):
   if 10000 % i == 0:
      print "Not prime!"
      break

for i in xrange(2, 10000/2):
  if 10000 % i == 0:
     print "Not prime!"
     break

the second will execute much faster for the simple reason that it only generates one number: 2. The top, OTOH, generates the entire list [2,3,4,5...4999]

Jeff

[jrcagle]

I like the 'not dividing by multiples of 2 and 3' optimization. Can you extend that to multiples of 5? 7? Perhaps even you could generalize it to multiples of any prime.

I also like the 'not going past half the number' optimization. Math challenge: given n, what's the smallest number that you need to test to know whether n is prime? That will give you the optimal optimization.

Jeff

[bumsfeld]

What's slicing

Also, what's the difference between xrange and range?

Here are some slicing examples (takes a while to get it, but very powerful):

# slicing operator seq[begin : end : step]
# step is optional
# defaults are index begin=0, index end=len(seq)-1, step=1
# -begin or -end --> count from the end backwards
# step = -1 reverses sequence
 
a = [0,1,2,3,4,5,6,7,8]
# if you get lost, put in the defaults in your mind
print a[3:6] # [3, 4, 5]
print a[:3] # [0, 1, 2]
print a[5:] # [5, 6, 7, 8]
print a[-3:] # [6, 7, 8]
print a[2:-2] # [2, 3, 4, 5, 6]
print a[1::2] # [1, 3, 5, 7]
print a[::-1] # [8, 7, 6, 5, 4, 3, 2, 1, 0]
 
# makes true copy of list a
b = a[:]
 
b[2:5] = [77, 88]
print b # [0, 1, 77, 88, 5, 6, 7, 8]

The function range() returns the whole list requested, xrange() returns only the next possible value each time as you iterate in the for loop. This saves time and memory with large list ranges.

[Matt Tacular]

I also like the 'not going past half the number' optimization. Math challenge: given n, what's the smallest number that you need to test to know whether n is prime? That will give you the optimal optimization.

That's the train of thought I was going with during my last few posts when i optimized it with the one quarter thing. But the only exception was 9, due to 3 being the highest number you need to check, but that's at 1/3. Or the square root. And since you asked, I've thought about it and it seems to be the square root is the highest number that you need to check. Take 25 for example, the highest number you need to check is 5. But when the number doesn't have a whole number as a square, maybe I could round it up and only check up to there?

If you look at this, which is the current version of my generator, you can see that I was using that train of thought, but instead of square roots, I was just thinking that past 25% would be useless.

from __future__ import division

def main():
    num = input("How high to find prime numbers? ")
    li = [2]
    for i2 in xrange(3,(num+1),2):
        prime = True
        for i in xrange(3,((i2//4)+1),2):
            if i2 % i == 0:
                prime = False
                break
        if prime == True:
            li.append(i2)
    li.remove(9)
    print li
    
main()

while True:
    go_again = raw_input("Again?(y/n) ")
    if go_again.lower()[0] == "y":
        main()
    else:
        break

[Matt Tacular]

It does work, the square root thing. And I'm pretty sure this is the fastest I will get it for a while, but anyone who was interested in how fast it is. This one is a couple times faster than any of my other ones.

Test this one:

from __future__ import division
from math import *

def main():
    num = input("How high to find prime numbers? ")
    li = [2]
    for i2 in xrange(3,(num+1),2):
        prime = True
        sq = int('%.0f' % (float(sqrt(i2))))
        for i in xrange(3,(sq+1),2):
            if i2 % i == 0:
                prime = False
                break
        if prime == True:
            li.append(i2)
    print li
    
main()

while True:
    go_again = raw_input("Again?(y/n) ")
    if go_again.lower()[0] == "y":
        main()
    else:
        break

[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)

[arsham]

How this one compared to the other?

myarray = [2,3]
          
from math import sqrt
def prime(x):
    for i in xrange(3, x,2): 
        if filter(lambda x: i % x, myarray[0:int(sqrt(len(myarray)))]):
            myarray.append(i)