Java - Increasing performance of a simple prime number validator

Question

I'm in an intro to Java class and just finished an assignment, but I was left with a question in my head. I did not have time to ask my professor yet and it's a bit off topic from what we're doing anyhow.

Basically we had a program that will validate if a user inputted integer is prime or not. If it isn't prime, it calculates the closest prime number smaller than the input. For example:

Enter an integer: 4
4 is not a prime number. The closest prime number is 3.

The program works as intended using a loop if the input is not prime. Here is my code:

public static void main(String[] args) {

    Scanner input = new Scanner(System.in);
    int number;

    System.out.print("Please enter a positive, non-zero integer: ");
    number = input.nextInt();
    input.close();

    if (isValid(number) == true) {
        if(isPrime(number) == true) {
            System.out.printf("%d is a prime number.", number);
        } else {
            switch(number) {
                case 1: 
                    System.out.print("1 is not a prime number. \n");
                    System.out.print("We cannot find the nearest prime.");
                    break;
                default:
                    System.out.printf("%d is not a prime number.", number);
                    System.out.printf("\nThe nearest prime number is %d.", getNearestPrime(number));
                }
            }
        } else {
        System.out.print("Invalid input. Please run again.");
        System.exit(1);
    }   
}

public static boolean isValid(int number) {

    if (number > 0) {
        return true;
    } else {
        return false;
    }
}

public static boolean isPrime(int number) {

    int i;
    if(number == 1) {
        return false;
    } else {
        for(i = 2; i < number; i++) {
            if(number%i == 0) {
                return false;
            }
        }
        return true;
    }
}

public static int getNearestPrime(int number) {

    do {
        number--;
    } while (isPrime(number) == false);

    return number;
}

It's important to note we were required to create the three methods listed below main.

My question is this: is there a way to increase performance when calculating larger ints in this scenario?

If I was to input 2,147,483,647, the program takes about 10 seconds to recognize it's prime. If I enter 2,147,483,646, it takes roughly the same time to find the closest prime.

I completely understand why this happens, but it seems like any high level Java applications I've used can computer way more complex things much faster than my simple program can.

I'm genuinely just curious how experienced programmers handle something like this. Thank you!

Answer 1

Several simple things you can change:

1) A prime number will never be even, so once you check if a number is divisible by two, you don't need to check if it is divisible by any other even number. So you can simplify your loop a little. (Just add an if statement to check if the number is 2 and then start i at three)

2) You only have to loop until the square root of the number.

  int i;
  if(number == 1) {
      return false;
  }
  if(number == 2) {
     return true; //2 is a prime number
  } 
  if (number % 2 == 0) {
     return false;
  }
  for(i = 3; i* i <= number; i+=2) {
      if(number%i == 0) {
          return false;
      }
  }
  return true;

Answer 2

Well one thing to note is that algorithmic wise there are more efficient algorithms to use. See this answer for details

Regarding implementation you can for example employ some tricks such as caching of recent results if you want to increase performance. A more efficient approach but perhaps outside the scope of a course would be to use a list of precalculated primes. You can find one in the internet or you can run a program once to precalculate them up to a given point.

Do note that this approach would trade off some memory for the sake of speed.