944,100 Members | Top Members by Rank

Ad:
  • Python Discussion Thread
  • Marked Solved
  • Views: 12677
  • Python RSS
You are currently viewing page 1 of this multi-page discussion thread
Jan 27th, 2007
0

My prime Number generator

Expand Post »
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
Last edited by Matt Tacular; Jan 27th, 2007 at 2:00 am.
Similar Threads
Reputation Points: 10
Solved Threads: 7
Unverified User
Matt Tacular is offline Offline
187 posts
since Jun 2006
Jan 27th, 2007
0

Re: My prime Number generator

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.

Last edited by Matt Tacular; Jan 27th, 2007 at 2:38 am.
Reputation Points: 10
Solved Threads: 7
Unverified User
Matt Tacular is offline Offline
187 posts
since Jun 2006
Jan 27th, 2007
0

Re: My prime Number generator

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
Reputation Points: 92
Solved Threads: 156
Practically a Master Poster
jrcagle is offline Offline
608 posts
since Jul 2006
Jan 27th, 2007
0

Re: My prime Number generator

I was thinking of making it quit the loop as soon as it found a factor that isn't one or the counter.
Reputation Points: 10
Solved Threads: 7
Unverified User
Matt Tacular is offline Offline
187 posts
since Jun 2006
Jan 27th, 2007
0

Re: My prime Number generator

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.
Reputation Points: 10
Solved Threads: 7
Unverified User
Matt Tacular is offline Offline
187 posts
since Jun 2006
Jan 28th, 2007
0

Re: My prime Number generator

I think your print to the display will be by far the slowest operation.
Reputation Points: 961
Solved Threads: 211
Nearly a Posting Maven
sneekula is offline Offline
2,413 posts
since Oct 2006
Jan 29th, 2007
0

Re: My prime Number generator

yea, ditch the printing and append it to a list and it'll be almost instant.
Last edited by a1eio; Jan 29th, 2007 at 4:55 am.
Reputation Points: 26
Solved Threads: 24
Junior Poster
a1eio is offline Offline
140 posts
since Aug 2005
Jan 29th, 2007
0

Re: My prime Number generator

Click to Expand / Collapse  Quote originally posted by a1eio ...
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.
Reputation Points: 404
Solved Threads: 180
Nearly a Posting Virtuoso
bumsfeld is offline Offline
1,422 posts
since Jul 2005
Jan 29th, 2007
0

Re: My prime Number generator

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.
Reputation Points: 10
Solved Threads: 7
Unverified User
Matt Tacular is offline Offline
187 posts
since Jun 2006
Jan 29th, 2007
0

Re: My prime Number generator


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
Reputation Points: 92
Solved Threads: 156
Practically a Master Poster
jrcagle is offline Offline
608 posts
since Jul 2006

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Python Forum Timeline: Where's Nemo?
Next Thread in Python Forum Timeline: Reversing a sentence





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC