Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By a tutor
  • 1 Post By johnsomeone

Math Help - prime number

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    india
    Posts
    17

    prime number

    actually , I want to write a code in which i want to find prime numbers upto 10^8 higher. Can you tell me any property of prime which can tell a particular number prime or not in the most efficient way ? my purpose is to find all prime up to 10^8. thanks if u can help me in this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: prime number

    Primality test - Wikipedia, the free encyclopedia

    and that page has a link to this page AKS primality test - Wikipedia, the free encyclopedia

    If you're doing a big block of numbers though perhaps some sort of sieve would be best.

    Generating primes - Wikipedia, the free encyclopedia
    Last edited by a tutor; October 25th 2012 at 02:04 PM.
    Thanks from nitin1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: prime number

    There are probably more clever ways, but the "Sieve of Eratosthenes" should work. And it's very easy to code.

    A simple program would require an array of 10^8 items, each with a 4 byte integer and a 1 byte flag (to check if the integer had been "hit"). That's 5 x 10^8 bytes, so would require about about 500 Megabytes of RAM. That's doable on most PCs. If that's too large, then you could shrink it by about 20% by making it a 1 bit flag (and likely writing more complicated code - it depends on the capabilities of the language you're using). If that's still too large, then you'd need to read/write to a file during the processing. Such file ops are a big performance hit, and so should be coded with some care - the reads and writes should both be done in big "chunks".

    Also, remember that to determine if a number is prime or not requires only looking at its potential divisibility by integers up to the square root of the number. In your case, you'd only need to check for divisibility by primes up to 10^4.
    Thanks from nitin1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2012
    From
    india
    Posts
    17

    Re: prime number

    i am already using sieve. It is taking too much time for 10^8 numbers. i want better than this. time out when i use sieve for greater than 10^8. So please optimize it more. thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: prime number

    Quote Originally Posted by nitin1 View Post
    i am already using sieve. It is taking too much time for 10^8 numbers. i want better than this. time out when i use sieve for greater than 10^8. So please optimize it more. thanks
    You'll have to do the optimizing yourself. Post your code if you want some suggestions.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: prime number

    The links in atutor's post can point you to other methods (one's which I'm unfamiliar with) that might better serve your needs.
    For speeding up the Sieve of Eratosthenes, other than seeing how you're writing the code, I can give a few suggestions (though you might have already used them).
    1) Use a compiled language, C, C++, maybe even Assembly given how simple the routine is. Java and .NET have a lot of overhead for computationally intensive code.
    2) When you come to a new integer to "sieve with", if it's already been flagged as a composite integer, then you don't need to do it, and can skip to the next one.
    3) Since any composite has already been flagged as such by the time you've gotten to a prime greater than its square root, you can always start your process at a number squared. In other words, say you're about to "sieve" using the prime 79. You don't need to start at 79 x 2. You should start checking at 79x79, then 79 x 80, then 79 x81, etc.. I don't think this will make a big difference, but it will help.
    4) You could write code that saves and loads the sieve process at various stages of completion. You'd certainly want to consider this if the running time was much more than several hours. It would suck to have your computer crash or the power go out and lose all that work.
    5) When things become computationally demanding, understanding your compiler is important. Two different ways of writing "the same thing" - even if they seem like they should be "the same" in performance - might turn out to be noticably different in performance when your routine is running for hours and hours. Do you declare a variable inside a loop or outside of it for best performance? These kinds of little things that we usually ignore start to really matter when the numbers get this big.
    6) Shut down all other non-essential programs & services while this is running. Certainly kill your internet connection. Don't let anything annoying like your virus checker start a pre-scheduled scan.

    Remember that the number of "hits" - identifications of a composite as such for the first time - will decrease as the algorithm proceeds. The code to flag as a composite will therefore be skipped much more often as the routine runs. When you start with 2, that code fires for half the numbers up to 10^8. At 3, it only executes for 1/6 the numbers up to 10^8. Again, this is relatively minor, but between this and, when "sieving on p", starting at p-squared rather than px2, it should run slightly faster the values become greater.

    Put a timer in your code, and see how long it took you to reach (for sieving) the prime 101 (this is while checking through all numbers up to 10^8). The total time will be, roughly, 100 times longer (remember that you'll stop when you hit 10^4). If it takes an hour, then expect the total run to be 100 hours = 4+ solid days. If it takes 5 minutes, then the total run time will be about 8 hours.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 12:23 PM
  2. Is this a prime number??
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 25th 2011, 10:24 AM
  3. Prime number
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 1st 2010, 04:53 AM
  4. Replies: 1
    Last Post: September 2nd 2009, 09:31 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum