


Thread Tools  Display Modes 
Dec 11th, 2011, 2:07 PM  #1 
Newbie
Join Date: Dec 2011
Posts: 10
Rep Power: 0

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.
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. 
Dec 11th, 2011, 2:21 PM  #2 
Newbie
Join Date: Dec 2011
Posts: 1
Rep Power: 0

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 
Dec 11th, 2011, 2:34 PM  #3 
Programming Guru

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. 
Dec 11th, 2011, 3:02 PM  #4 
Newbie
Join Date: Dec 2011
Posts: 10
Rep Power: 0

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. 
Dec 11th, 2011, 3:25 PM  #5 
Programming Guru

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. 
Dec 11th, 2011, 3:58 PM  #6  
Hobby Coder
Join Date: May 2006
Posts: 1,181
Rep Power: 11

Re: Finding prime numbers in Python
Quote:
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. 

Dec 11th, 2011, 9:47 PM  #7 
Programming Guru

Re: Finding prime numbers in Python
@bden: I now realize that you probably thought I was telling you to use some prewritten '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 preprocessing, 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 10:02 PM. 
Dec 12th, 2011, 1:32 AM  #8 
CS  Math Student
Join Date: Jan 2009
Location: Belgrade
Posts: 280
Rep Power: 8

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. 
Dec 12th, 2011, 7:54 AM  #9  
Hobby Coder
Join Date: May 2006
Posts: 1,181
Rep Power: 11

Re: Finding prime numbers in Python
Quote:
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. 

Dec 12th, 2011, 1:23 PM  #10 
Programming Guru

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, reusing information across each call.If this isn't obvious is to you, then please reread 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. 
Bookmarks 
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)  
Thread Tools  
Display Modes  


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 4:24 PM 
Recuration Prime Numbers  techidiot  C  4  May 13th, 2010 4:40 PM 
Finding magic numbers  valleymorning  C++  15  Sep 5th, 2009 5:56 PM 
finding prime using bool  gmann145  C++  5  Feb 14th, 2008 5:19 PM 
Prime Numbers  Konnor  C++  6  Sep 12th, 2005 6:46 PM 