Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Dec 11th, 2011, 3:07 PM   #1
bden
Newbie
 
Join Date: Dec 2011
Posts: 10
Rep Power: 0 bden is on a distinguished road
Finding prime numbers in Python

I am working to teach myself programming but as you can imagine it can be difficult at times with no help and no previous training. I have never taken any programming classes or read any books. I have only watched the first 3 of a series of MIT online courses that can be found on youtube for the intro to programming 600 class.

The assignment is to create code that finds the 1000th prime number. I have tried many different approaches but always get stuck.


x=100000
divisors = () # empty tuple
for i in (1,x):
if (i%2) != 0: ## this indicates an odd number but do not know where to go to see if it is also prime
i = i+1



I am trying to assign an arbitrarily high number to x to begin searching for values because in the end I will just use a get method like divsors[999] to display the 1000th prime number. So, I said here, for every i in the range from (1,x) that if it cannot be divided by 2 with a remainder of 0 then it must be odd. Here is where I get stuck. The only way I can imagine to check whether odd numbers are prime is to continue to divide them by other numbers to see if any remainder of 0 is revealed. I do not know how to implement this method into code.

Ultimately I wanted to find the odds, determine from this set which is prime and add it to the tuple 'divisors.'
Please bear in mind the only thing I have been versed in(and not very much!) is:
For statements, while statements, and conditionals(not very much). So my arsenal is quite limited.
bden is offline   Reply With Quote
Old Dec 11th, 2011, 3:21 PM   #2
TheCrownedFox
Newbie
 
Join Date: Dec 2011
Posts: 1
Rep Power: 0 TheCrownedFox is on a distinguished road
Re: Finding prime numbers in Python

you might want to look into the sieve of eratosthenes, its what I used when I did something similar.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
TheCrownedFox is offline   Reply With Quote
Old Dec 11th, 2011, 3:34 PM   #3
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 15 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Finding prime numbers in Python

The Sieve of Eratosthenes is indeed an easy and efficient way to go about this, but you might also want to take time to understand how to get your first approach working.

You seem to be trying to do too much in one shot. You should first start by making an is_prime(x) function, which returns True if and only if 'x' is prime. This should be relatively simple. Loop, and return False if it's composite. Otherwise, the loop will exhaust and you should return True.

Now that you have this building block, loop through numbers, using the is_prime function to find the 1st, then the 2nd, all the way up to the 1000th. Computers are fast. It will do this relatively quickly.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Old Dec 11th, 2011, 4:02 PM   #4
bden
Newbie
 
Join Date: Dec 2011
Posts: 10
Rep Power: 0 bden is on a distinguished road
Re: Finding prime numbers in Python

Well, there are almost certainly functions for doing this. This approach was a more brute force method where I had to essentially define what I was looking for:
i.e When i/2 != 0 then it must be odd. Then to take these odds and define which of them are prime.

Using the prime function already 'knows' what numbers are prime if you follow what I am trying to say.
bden is offline   Reply With Quote
Old Dec 11th, 2011, 4:25 PM   #5
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 15 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Finding prime numbers in Python

I don't quite see what the problem is then. If there's an easier way to code it, and that code executes relatively quickly (either of the solutions in my above post should take on the order of tens of milliseconds if implemented correctly), then why not do it that way? This is especially true for someone new to programming. Nail down the techniques of properly writing code, and use algorithms that make sense to you and your readers.

If you're looking for something "cleverer" than using an is_prime function, then the prime sieve is essentially that.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Old Dec 11th, 2011, 4:58 PM   #6
Adak
Hobby Coder
 
Join Date: May 2006
Posts: 1,181
Rep Power: 10 Adak will become famous soon enough
Re: Finding prime numbers in Python

Quote:
Originally Posted by bden View Post
I am working to teach myself programming but as you can imagine it can be difficult at times with no help and no previous training. I have never taken any programming classes or read any books. I have only watched the first 3 of a series of MIT online courses that can be found on youtube for the intro to programming 600 class.

The assignment is to create code that finds the 1000th prime number. I have tried many different approaches but always get stuck.


x=100000
divisors = () # empty tuple
for i in (1,x):
if (i%2) != 0: ## this indicates an odd number but do not know where to go to see if it is also prime
i = i+1



I am trying to assign an arbitrarily high number to x to begin searching for values because in the end I will just use a get method like divsors[999] to display the 1000th prime number. So, I said here, for every i in the range from (1,x) that if it cannot be divided by 2 with a remainder of 0 then it must be odd. Here is where I get stuck. The only way I can imagine to check whether odd numbers are prime is to continue to divide them by other numbers to see if any remainder of 0 is revealed. I do not know how to implement this method into code.

Ultimately I wanted to find the odds, determine from this set which is prime and add it to the tuple 'divisors.'
Please bear in mind the only thing I have been versed in(and not very much!) is:
For statements, while statements, and conditionals(not very much). So my arsenal is quite limited.
Your approach is called "Trial by Division". It is more efficient if you:

1. Handle the number two before the loop of candidate prime numbers begins.
2. Start the candidate number at 3, inside the candidate prime number loop.
3. Increment this loop by 2 (3,5,7,9,11 etc.) so even numbers are skipped
4. In your testing loop for the candidate prime number, you may stop the testing when the test number is equal (not less than, equal), the square root of the candidate prime number.
5. If you save your primes as you find them, then you can test using ONLY the lower primes, themselves. (Still with only the primes less than or equal to the square root of the prime candidate number). This is the Fundamental Arithmetic Theorem. Every number is either a multiple of the primes less than itself (a composite number), or it is itself, prime.

6. Find the square root just once, outside of the testing loop. Assign it to a variable, to use for repeated testing.

Although this algorithm is fast with the lower prime numbers, it bogs down when the testing gets into primes candidates > 1 Million. These are the more interesting primes. To work with larger primes, or to find the primes 10X faster, use the Sieve of Eratosthenes. There are several ways of optimizing it for greater speed.

Using an isPrime() function for the testing loop, is the norm. A nested for loop can work as well.
Adak is offline   Reply With Quote
Old Dec 11th, 2011, 10:47 PM   #7
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 15 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Finding prime numbers in Python

@bden: I now realize that you probably thought I was telling you to use some pre-written 'is_prime' function. To be clear, I was suggesting that you write your own 'is_prime' function, because I felt like you were trying to tackle both problems in one go. Again, write an 'is_prime' function naively, and then apply that to the original problem separately. One step at a time for simplicity.

@Adak: The Sieve of Eratosthenes doesn't find primes faster. In fact, it finds them slower (even slower than the naive iteration up to the square root). The difference is it finds and classifies all of the primes/composites simultaneously, which allows you to more efficiently find the k'th prime (or to make is_prime queries after the initial pre-processing, in constant time, giving a better overall ("amortized") cost), as opposed to if you were to try to test the primality of a whole slew of candidates independently.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.

Last edited by Sane; Dec 11th, 2011 at 11:02 PM.
Sane is offline   Reply With Quote
Old Dec 12th, 2011, 2:32 AM   #8
S.I
CS | Math Student
 
S.I's Avatar
 
Join Date: Jan 2009
Location: Belgrade
Posts: 280
Rep Power: 6 S.I is on a distinguished road
Re: Finding prime numbers in Python

I have to agree with Sane here,...

@bden
All you need for now, is to try and implement regular naive methods (described here)
If you then become interested in better more efficient algorithms, you can find some of them mentioned also in the link above.

Make small steps, ...
__________________
--
Artificial Intelligence and Automated Stupidity.
Mathematics is the language of nature.
S.I is offline   Reply With Quote
Old Dec 12th, 2011, 8:54 AM   #9
Adak
Hobby Coder
 
Join Date: May 2006
Posts: 1,181
Rep Power: 10 Adak will become famous soon enough
Re: Finding prime numbers in Python

Quote:
Originally Posted by Sane View Post

@Adak: The Sieve of Eratosthenes doesn't find primes faster. In fact, it finds them slower (even slower than the naive iteration up to the square root). The difference is it finds and classifies all of the primes/composites simultaneously, which allows you to more efficiently find the k'th prime (or to make is_prime queries after the initial pre-processing, in constant time, giving a better overall ("amortized") cost), as opposed to if you were to try to test the primality of a whole slew of candidates independently.
The Sieve of Eratosthenes doesn't "find all the primes/composites simultaneously". It uses a nested pair of for loops, as do the Trial by Division programs. It finds multiplies of one prime at a time, and marks them off, one at a time.

Is it faster or slower than a Trial by Division type of program, for testing the primality of a whole slew of candidates independently? If you implement the "wheel" optimization in the Sieve of Eratosthenes program, it will be faster than a Trial by Division program, but this is just my opinion - I have not tested this.
Adak is offline   Reply With Quote
Old Dec 12th, 2011, 2:23 PM   #10
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Google / Kitchener
Posts: 4,154
Rep Power: 15 Sane has a spectacular aura aboutSane has a spectacular aura about
Send a message via MSN to Sane
Re: Finding prime numbers in Python

Seems like you misunderstood what I was saying. To simplify my last post: the Sieve does not compute is_prime(x) faster than trial division (this should be obvious). However, it does compute for i : 1 .. n: is_prime(i) (i.e. all primes/composites simultaneously) faster than 'n' independent 'is_prime' calls, by nature of, in effect, re-using information across each call.

If this isn't obvious is to you, then please re-read my previous post and the Wikipedia articles on this subject.
__________________
PFO's Folding@Home Team | Sane's Monthly Algorithms Challenges
Rules | How to Post a Question | How to Post Code

Becoming a good programmer requires foresight of your code's execution.
Becoming an excellent programmer requires foresight of your code's modification.
Sane is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

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

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
how to find prime numbers and armstrong numbers from a series of fibonacci numbers? n75 Bash / Shell Scripting 1 Dec 8th, 2011 5:24 PM
Recuration Prime Numbers techidiot C 4 May 13th, 2010 5:40 PM
Finding magic numbers valleymorning C++ 15 Sep 5th, 2009 6:56 PM
finding prime using bool gmann145 C++ 5 Feb 14th, 2008 6:19 PM
Prime Numbers Konnor C++ 6 Sep 12th, 2005 7:46 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 10:16 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC