1 2 Previous Next 28 Replies Latest reply: Apr 2, 2008 1:53 AM by EJP RSS

    Finding if a number is prime

    807591
      hello,

      Does anyone have codes snippets that can find if a number is a Prime or not?

      I'll be glad to have such code.

      Regards,
      Socx
        • 1. Re: Finding if a number is prime
          800322
          Does anyone have codes snippets that can find if a
          number is a Prime or not?
          Sure. Ptretty common homework.
          I'll be glad to have such code.
          I can tell. What do you need it for?
          • 2. Re: Finding if a number is prime
            abillconsl
            You can check out [url http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm#_The_Obvious_Method_for_Finding_Primes]Fun With Prime Numbers
            • 3. Re: Finding if a number is prime
              807591
              you can tell if a number is prime if its not divisible by any number less then itself except for 1.
              • 4. Re: Finding if a number is prime
                807591
                How fast does it run. There are many many faster ways to do this.....depending on the range of numbers you're working on....but here's a simple way to do it. This is more of a number theory question, not a java question.
                public static void main(String[] args)
                    {
                        long number = 465464623;
                        long result = isPrime( number );
                        System.out.println( result != -1 ? "Is not prime....divisible by "
                            + result : "PRIZIME" );
                    }
                
                
                    private static long isPrime(long x)
                    {
                        for ( int i = 2; i < Math.sqrt( x ); i++ )
                        {
                            if ( x % i == 0 )
                            {
                                return i;
                            }
                        }
                        return -1;
                    }
                • 5. Re: Finding if a number is prime
                  807591
                  you can tell if a number is prime if its not
                  divisible by any number less then itself except for 1.
                  Don't even need to chack that many numbers.
                  • 6. Re: Finding if a number is prime
                    doremifasollatido
                    you can tell if a number is prime if its not
                    divisible by any number less then itself except for 1.
                    Don't even need to chack that many numbers.
                    Once you check for divisibility by 2, you only need to test odd numbers.
                    • 7. Re: Finding if a number is prime
                      807591
                      you can tell if a number is prime if its not
                      divisible by any number less then itself except
                      for 1.
                      Don't even need to chack that many numbers.
                      Once you check for divisibility by 2, you only need
                      to test odd numbers.
                      Actually....you only need to ever check divisability by prime numbers up to the square root of the number. If you want to brute force it.
                      • 8. Re: Finding if a number is prime
                        800282
                        Norweed, your method is incorrect. Take any prime number and multiply it with itself. These numbers will pass your test as being prime as well.

                        @OP: here's a nice method to test numbers for primatlity:
                        public boolean isPrime(long number) {
                          return new java.math.BigInteger(String.valueOf(number)).isProbablePrime(100);
                        }
                        • 9. Re: Finding if a number is prime
                          807591
                          Norweed, your method is incorrect. Take any prime
                          number and multiply it with itself. These numbers
                          will pass your test as being prime as well.

                          @OP: here's a nice method to test numbers for
                          primatlity:
                          public boolean isPrime(long number) {
                          return new
                          java.math.BigInteger(String.valueOf(number)).isProbab
                          ePrime(100);
                          }
                          Make it <=....no biggy. isProbablePrime won't tell you if it's prime or not...only if it's likely a prime.
                          • 10. Re: Finding if a number is prime
                            800282
                            > Make it <=....no biggy.

                            Of course it's a biggy. The first method returns wrong answers.


                            > isProbablePrime won't tell
                            you if it's prime or not...only if it's likely a
                            prime.

                            I know what probable means.
                            • 11. Re: Finding if a number is prime
                              807591
                              > Make it <=....no biggy.

                              Of course it's a biggy. The first method returns
                              wrong answers.


                              > isProbablePrime won't tell
                              you if it's prime or not...only if it's likely a
                              prime.

                              I know what probable means.
                              Anal buggers all over the place. I didn't unit test it for squares of primes...just typed something up and threw it out there...sorry for the lack of testing and reflection on all code I post.....good catch, but i was refering to the mistake as not being that big of a deal. I wasn't infering that it worked or anything.
                              • 12. Re: Finding if a number is prime
                                JosAH
                                Norweed, your method is incorrect. Take any prime
                                number and multiply it with itself. These numbers
                                will pass your test as being prime as well.

                                @OP: here's a nice method to test numbers for primatlity:
                                > > public boolean isPrime(long number) { return new
                                java.math.BigInteger(String.valueOf(number)).isProbabePrime(100);
                                }
                                Make it <=....no biggy. isProbablePrime won't tell
                                you if it's prime or not...only if it's likely a prime.
                                Better yet, make it:
                                for ( int i = 2; i*i <= x ); i++ )
                                btw, for simple 32 bit ints the probablePrime method is exact.

                                kind regards,

                                Jos
                                • 13. Re: Finding if a number is prime
                                  800282
                                  > Anal buggers all over the place.

                                  ?
                                  Where did I call you names?


                                  > I didn't unit test
                                  it for squares of primes...just typed something up
                                  and threw it out there...sorry for the lack of
                                  testing and reflection on all code I post.....

                                  Never said you should. A lot of the code I post contains (design) errors.


                                  > good catch, but i was refering to the mistake as not being
                                  that big of a deal. I wasn't infering that it worked
                                  or anything.

                                  I though you meant by "no biggy" that it didn't really matter if the squared prime's weren't labelled as prime.
                                  Why the hostility?
                                  • 14. Re: Finding if a number is prime
                                    JosAH
                                    I didn't unit test it for squares of primes...just typed something up
                                    and threw it out there...
                                    So don't do that. Software development is an exact and precise process.
                                    It's a science actually. Sloppy code jamming is worse than no code at all.

                                    Jos
                                    1 2 Previous Next