7
\$\begingroup\$

Is this the most efficient way to find if a number is prime? I can't think of a better way and it seems to run pretty quickly.

    public boolean primes(int num){
    for(int i = 2; i < num; i++){
        if(num % i == 0){
            System.out.println(num + " is not prime");
            return false;
        }
    }
    System.out.println(num + " is prime");
   return true; 
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Probably even the deterministic variant of Miller-Rabin primality testing is much faster. \$\endgroup\$
    – Brian
    Apr 4 '13 at 13:16
  • \$\begingroup\$ Have you checked Ferma tests or variants? e.g. here is nice discussion \$\endgroup\$ Apr 5 '13 at 12:18
  • \$\begingroup\$ This is my favorite discussion of primality testing: stackoverflow.com/questions/9625663/… \$\endgroup\$
    – gsingh2011
    Apr 10 '13 at 20:54
  • 2
    \$\begingroup\$ I have asked this question to be closed as asking for more efficient primarily testing is not code review related. Having side effects in this code is definitely code review related. What is "System.out.println" doing in middle of a Boolean method? \$\endgroup\$
    – jimjim
    Aug 4 '17 at 6:27
21
\$\begingroup\$

A faster method would be to skip all even numbers and only try up to the square root of the number.

public static boolean isPrime(int num){
    if ( num > 2 && num%2 == 0 ) {
        System.out.println(num + " is not prime");
        return false;
    }
    int top = (int)Math.sqrt(num) + 1;
    for(int i = 3; i < top; i+=2){
        if(num % i == 0){
            System.out.println(num + " is not prime");
            return false;
        }
    }
    System.out.println(num + " is prime");
    return true; 
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ The code is very good and is just what I did at first. Then I realized that there is no point in adding 1 to the sqrt of num. And of course the printing makes it less efficient, as it is already returning the boolean value. \$\endgroup\$
    – user58179
    Nov 15 '14 at 4:21
  • \$\begingroup\$ It prints 1 as a prime number which is not a prime number. \$\endgroup\$
    – arsenal
    Dec 16 '15 at 23:52
  • \$\begingroup\$ the first if statement should be: if(num <= 2 || num%2 == 0){ return false; } \$\endgroup\$
    – LeTex
    Mar 19 '17 at 8:55
  • 1
    \$\begingroup\$ please refactor this code, it is a bad example of a code that is just suppose to return a true, false but it is having side effects, what is System.out.println doing in middle of a function? \$\endgroup\$
    – jimjim
    Aug 4 '17 at 6:21
  • \$\begingroup\$ This method runs for all odd numbers from 3 to sqrt of input number. But this can be even more improved if we only divide with prime numbers in that range. For example; If we are checking for number 131, it makes sense to try to divide it using 3 but does not make sense to divide it with 9. Because if its not divisible by 3 it will never be divisible by 9. \$\endgroup\$ Feb 3 '19 at 6:43
3
\$\begingroup\$

This is what I did:

public static boolean isPrime(int n) {

        if((n > 2 && n % 2 == 0) || n == 1) {
            return false;
        }

        for (int i = 3; i <= (int)Math.sqrt(n); i += 2) {

            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

In the first if test, I put the (n > 2 && n % 2 == 0)first, because I think that would short-circuit the || and that evaluation will come more often than n == 1 so it should skip that and become true a little bit faster than doing it the other way around.

Also, like Tom pointed out in the accepted answer, you start countin at 3, in order to remove the addition of 1 to the square root, I had to use i <= (int)Math.sqrt(n) otherwise it blows up, I don't know why.

I tested my code with the first 10 thousand primes and it seems ok as I get 104,729 as the 10,000th number, which is correct, it gets the result in 1.324 seconds, which I'm not sure if it's fast or not.

Note:

As ferhan pointed out, with the accepted answer it says that 1 is a prime number, which is not. But with the suggestion from LeTex, I get a weird result and not the correct answer.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thank you for not having used side effects in middle of the method as the accepted answer has done. but just like the accepted answer, this too is far from efficient. But I'll raise that with the question poster instead. \$\endgroup\$
    – jimjim
    Aug 4 '17 at 6:25
  • \$\begingroup\$ @Arjang I still have a long way to learn how to code correctly, and I'd really appreciate it if you could point me in the right direction on how to make this code more efficient, thanks in advance. \$\endgroup\$ Aug 4 '17 at 17:54
  • 1
    \$\begingroup\$ Lord Anubis, god of the under world. Making that particular code efficient is like trying to make bubble sort more efficient, you wont do that. To make that code better though, you already have removed side effects, some how making it simpler but most of all looking up primarility testing to see more efficient ways of doing it. Not all code can be made better, sometimes abandon the code and start clean, separate knowledge domain related problems from structural code problems, also look up "clean code" book, SOLID,DRY methodologies, design patterns. \$\endgroup\$
    – jimjim
    Aug 4 '17 at 21:26
  • \$\begingroup\$ also follow the links under the question, at the top of the page. \$\endgroup\$
    – jimjim
    Aug 4 '17 at 21:29
0
\$\begingroup\$

This program is an efficient one. I have added one more check-in if to get the square root of a number and check is it divisible or not if it's then its not a prime number.

public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
        int T; // number of test cases
        T = sc.nextInt();
        long[] number = new long[T];
        if(1<= T && T <= 30){
        for(int i =0;i<T;i++){
            number[i]=sc.nextInt(); // read all the numbers
        }
        for(int i =0;i<T;i++){
            if(isPrime(number[i]))
                System.out.println("Prime");
            else
               System.out.println("Not prime");    
        }
    }
    else
      return;
    }
    // is prime or not
    static boolean isPrime(long num){
        if(num==1)
          return false;
        if(num <= 3)
          return true;
        if(num % 2 == 0 || num % 3 == 0 || num % (int)Math.sqrt(num) == 0)
          return false;  
        for(int i=4;i<(int)Math.sqrt(num);i++){
            if(num%i==0)
              return false;
        }
       return true;     
    }
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.