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

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.

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

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

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.

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

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.

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.

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