My prime Number generator

[Matt Tacular]

Can someone look at this and tell me if it actually is doing what it's supposed to.
[php]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[/php]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 [php]"if len(li) <= 2:" to "if len(li) == 2:"[/php]

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.[php]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[/php]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.

[php]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[/php]

[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