| | |
My prime Number generator
Thread Solved |
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
[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
Last edited by Matt Tacular; Jan 27th, 2007 at 2:00 am.
•
•
Join Date: Jul 2006
Posts: 608
Reputation:
Solved Threads: 150
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
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 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.
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.
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.
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.
•
•
Join Date: Jul 2006
Posts: 608
Reputation:
Solved Threads: 150
•
•
•
•
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.

Seriously, the program is good; the sieve recommendation is just for "further study."
Jeff
![]() |
Similar Threads
Other Threads in the Python Forum
- Previous Thread: Where's Nemo?
- Next Thread: Reversing a sentence
| Thread Tools | Search this Thread |
alarm ansi app assignment avogadro backend beginner binary bluetooth character cmd customdialog cx-freeze data decimals dictionary directory dynamic error exe file float format function generator getvalue gnu graphics halp heads homework http ideas import input ip itunes java leftmouse line linux list lists loop maintain maze millimeter module mouse number numbers output parsing path pointer port prime programming progressbar push py2exe pygame python queue random recursion schedule screensaverloopinactive script scrolledtext slicenotation sqlite ssh statistics string strings sudokusolver sum text thread threading time tlapse tuple tutorial ubuntu unicode url urllib urllib2 variable variables ventrilo vigenere web webservice wikipedia write wxpython xlib






