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]

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.

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.

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.

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

Jeff

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

replace: With

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

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

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: With

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.