User Name Password Register
DaniWeb IT Discussion Community
All
What is DaniWeb IT Discussion Community?
You're currently browsing the Python section within the Software Development category of DaniWeb, a massive community of 397,810 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,515 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our Python advertiser:
Views: 7628 | Replies: 38
Reply
Join Date: Jun 2006
Location: America
Posts: 186
Reputation: Matt Tacular is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 2
Matt Tacular's Avatar
Matt Tacular Matt Tacular is offline Offline
Junior Poster

My prime Number generator

  #1  
Jan 27th, 2007
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 1:00 am.
AddThis Social Bookmark Button
Reply With Quote  
Join Date: Jun 2006
Location: America
Posts: 186
Reputation: Matt Tacular is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 2
Matt Tacular's Avatar
Matt Tacular Matt Tacular is offline Offline
Junior Poster

Re: My prime Number generator

  #2  
Jan 27th, 2007
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 1:38 am.
Reply With Quote  
Join Date: Jul 2006
Posts: 562
Reputation: jrcagle is on a distinguished road 
Rep Power: 4
Solved Threads: 72
jrcagle jrcagle is offline Offline
Posting Pro

Re: My prime Number generator

  #3  
Jan 27th, 2007
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
Reply With Quote  
Join Date: Jun 2006
Location: America
Posts: 186
Reputation: Matt Tacular is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 2
Matt Tacular's Avatar
Matt Tacular Matt Tacular is offline Offline
Junior Poster

Re: My prime Number generator

  #4  
Jan 27th, 2007
I was thinking of making it quit the loop as soon as it found a factor that isn't one or the counter.
Reply With Quote  
Join Date: Jun 2006
Location: America
Posts: 186
Reputation: Matt Tacular is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 2
Matt Tacular's Avatar
Matt Tacular Matt Tacular is offline Offline
Junior Poster

Re: My prime Number generator

  #5  
Jan 27th, 2007
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.
Reply With Quote  
Join Date: Oct 2006
Posts: 1,193
Reputation: sneekula is on a distinguished road 
Rep Power: 4
Solved Threads: 38
sneekula's Avatar
sneekula sneekula is offline Offline
Veteran Poster

Re: My prime Number generator

  #6  
Jan 28th, 2007
I think your print to the display will be by far the slowest operation.
No one died when Clinton lied.
Reply With Quote  
Join Date: Aug 2005
Location: England - York
Posts: 136
Reputation: a1eio is an unknown quantity at this point 
Rep Power: 4
Solved Threads: 9
a1eio's Avatar
a1eio a1eio is offline Offline
Junior Poster

Re: My prime Number generator

  #7  
Jan 29th, 2007
yea, ditch the printing and append it to a list and it'll be almost instant.
Last edited by a1eio : Jan 29th, 2007 at 3:55 am.
Reply With Quote  
Join Date: Jul 2005
Location: France
Posts: 980
Reputation: bumsfeld is an unknown quantity at this point 
Rep Power: 5
Solved Threads: 43
bumsfeld's Avatar
bumsfeld bumsfeld is offline Offline
Posting Shark

Re: My prime Number generator

  #8  
Jan 29th, 2007
Originally Posted by a1eio View Post
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.
Reply With Quote  
Join Date: Jun 2006
Location: America
Posts: 186
Reputation: Matt Tacular is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 2
Matt Tacular's Avatar
Matt Tacular Matt Tacular is offline Offline
Junior Poster

Re: My prime Number generator

  #9  
Jan 29th, 2007
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.
Reply With Quote  
Join Date: Jul 2006
Posts: 562
Reputation: jrcagle is on a distinguished road 
Rep Power: 4
Solved Threads: 72
jrcagle jrcagle is offline Offline
Posting Pro

Re: My prime Number generator

  #10  
Jan 29th, 2007
Originally Posted by Matt Tacular View Post

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
Reply With Quote  
Reply

Only community members can participate in forum threads. You must register or log in to contribute.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 

DaniWeb Python Marketplace
Thread Tools Display Modes

Similar Threads
Other Threads in the Python Forum

All times are GMT -4. The time now is 6:25 am.
Forum system based on vBulletin Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
©2003 - 2008 DaniWeb® LLC