Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] testing if 32 bit integer is prime number

Expand Messages
  • Phil Carmody
    ... Tere Ylar, ... Think of 25... So you could add another check for divisibility by 5. Then think of 49. Hmmm, looks like you need to go a bit further... ...
    Message 1 of 5 , Oct 2, 2001
    • 0 Attachment
      On Tue, 02 October 2001, ylar.jyrviste@... wrote:
      > Hi,

      Tere Ylar,

      > I need to show if a 32 bit integer is prime or not. Is it enough to
      > prove that the number is greater than 2,odd number and divisible by 3?

      Think of 25...
      So you could add another check for divisibility by 5.
      Then think of 49.
      Hmmm, looks like you need to go a bit further...

      > Or is there another simple algorithm to prove it(I hvae to implement
      > it in assembler)

      You have made the first few steps, the extension is to test all primes up to and including the square root of the number you want to test (equivalently - until p squared is larger than the number you're testing). For 32bit numbers this isn't too lengthy a process, but don't try it for larger numbers. The process is called 'wheel factoring', 'trial division', or simply 'brute force'.

      Another question is how to generate all the primes easily.
      There are two equally simple answers:
      1) write a quick sieve to generate all primes up to 16-bits (which can be done really easily if you already know all primes up to 8-bits). See the Prime Pages for information on such a sieve:
      http://www.utm.edu/research/primes/glossary/SieveOfEratosthenes.html

      2) Don't bother - simply be prepared to be a bit wasteful with your tests.
      Trial divide by 2 and 3 first, then after that trial divide by
      6n-1 and 6n+1 for every n>=1 (so that's 5, 7, then 11, 13, then 17, 19, then 23, 25 (wasteful - already done 5) ...)
      The above optimisation can be extended to
      first do trial division by 2, 3, 5, 7, 11 and 13
      then do trial division by 30n-13, 30n-11, 30n-7, 30n-1, 30n+1, 30n+7, 30n+11, 30n+13 for each n>=1.

      Oh, and when I say 'every' or 'each' above, you are permitted to stop as soon as you find a factor!

      There's more info about factoring, and some sample code at
      http://www.frenchfries.net/paul/factoring/
      There's more info about primality proving in general on the Prime Pages http://primepages.org/
      but we're always here to answer questions too.


      N�gemist,
      Phil

      Mathematics should not have to involve martyrdom;
      Support Eric Weisstein, see http://mathworld.wolfram.com
      Find the best deals on the web at AltaVista Shopping!
      http://www.shopping.altavista.com
    • Paul Leyland
      ... You mean *not* divisible by 3, otherwise it certainly isn t prime. Even that s not good enough. Consider 25: odd, 2 and not divisible by 3. It s not
      Message 2 of 5 , Oct 2, 2001
      • 0 Attachment
        > I need to show if a 32 bit integer is prime or not. Is it enough to
        > prove that the number is greater than 2,odd number and divisible by 3?

        You mean *not* divisible by 3, otherwise it certainly isn't prime.

        Even that's not good enough. Consider 25: odd, >2 and not divisible by
        3. It's not prime either.

        >
        > Or is there another simple algorithm to prove it(I hvae to implement
        > it in assembler)


        There are many simple algorithms. Without knowing your constraints,
        it's hard to give definite advice. The answers to the following
        questions should guide you:

        Can the input number be negative?
        Although the input number may be 32 bits, are all 2^32 values possible?
        Are you optimizing for speed, for data space, for program size, for
        simplicity of programming or what?


        If you have a lot of data storage, for instance, you could have a very
        large table of primes and index into it to see whether a given value is
        prime or not.


        Paul
      • James Thoms
        May I suggest that you use strong pseudoprimes as described in http://www.utm.edu/research/primes/prove/prove2_3.html It may seem a bit more complex then the
        Message 3 of 5 , Oct 2, 2001
        • 0 Attachment
          May I suggest that you use strong pseudoprimes as described in
          http://www.utm.edu/research/primes/prove/prove2_3.html
          It may seem a bit more complex then the other methods, but requires almost
          no storage space and shouldn't be TOO difficult to implement. Specifically,
          you can use other people's work to reduce your workload by using bases 2, 7
          and 61, which can verify a number to be prime if it is less than 4759123141
          (more than 32 bits). Bitshifting can be used to take care of any necessary
          divisions by two and the modulus and exponentiation algorithms won't be very
          hard to implement in assembly (you would probably need a modulus or
          equivalent function for trial divisions anyway). At the very least, it is
          an interesting alternative to trial division.

          Hope this helps,

          James




          James Thoms
          3B Computer Engineering
          University of Waterloo



          From: ylar.jyrviste@...
          To: primenumbers@yahoogroups.com
          Subject: [PrimeNumbers] testing if 32 bit integer is prime number
          Date: Tue, 02 Oct 2001 11:58:19 -0000


          Hi,

          I need to show if a 32 bit integer is prime or not. Is it enough to
          prove that the number is greater than 2,odd number and divisible by 3?

          Or is there another simple algorithm to prove it(I hvae to implement
          it in assembler)

          Thanks

          a computer science student



          _________________________________________________________________
          Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp
        • Phil Carmody
          ... Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at
          Message 4 of 5 , Oct 2, 2001
          • 0 Attachment
            On Tue, 02 October 2001, "James Thoms" wrote:
            > May I suggest that you use strong pseudoprimes as described in
            > http://www.utm.edu/research/primes/prove/prove2_3.html
            > It may seem a bit more complex then the other methods, but requires almost
            > no storage space and shouldn't be TOO difficult to implement. Specifically,
            > you can use other people's work to reduce your workload by using bases 2, 7
            > and 61, which can verify a number to be prime if it is less than 4759123141
            > (more than 32 bits). Bitshifting can be used to take care of any necessary
            > divisions by two and the modulus and exponentiation algorithms won't be very
            > hard to implement in assembly (you would probably need a modulus or
            > equivalent function for trial divisions anyway). At the very least, it is
            > an interesting alternative to trial division.


            Good suggestion. Ready-made source code, by Professor Caldwell, in JavaScript, can be found at

            http://primes.utm.edu/curios/includes/file.php/primetest.html

            Phil

            Mathematics should not have to involve martyrdom;
            Support Eric Weisstein, see http://mathworld.wolfram.com
            Find the best deals on the web at AltaVista Shopping!
            http://www.shopping.altavista.com
          Your message has been successfully submitted and would be delivered to recipients shortly.