What is the best way to test for primality?

Hello everyone!

This question isn’t related to any specific lesson or exercise, but what would be the most efficient way to check whether or not a number is prime in Java?

A user would be prompted to input a number into the console and the program would determine and display whether or not the number inputted is prime.

This is what my current code looks like (definitely not the most efficient).

import java.util.Scanner;

public class PrimeNumber {

	public static void main(String[] args) {
		int num;
		Scanner sc = new Scanner(System.in);
		
		// Prompt the user for a number.
		System.out.print("Enter a number: ");
		num = sc.nextInt();
		sc.close();
		
		// Check and display if the number is prime.
		if (num <= 1) {
			System.out.println(num + " is not prime.");
		} else if (num == 2) {
			System.out.println(num + " is a prime number.");
		} else {
			for (int i = 2; i < num; i++) {
				if (num % i == 0) {
					System.out.println(num + " is not prime.");
					break;
				} else if (i == num - 1) {
					System.out.println(num + " is a prime number.");	
				}
			}
		}
		
	}

}
1 Like

Hello! I think-form what I’ve read, the best way is to check for primality up to the square root (rounded up) of a number. There may be other ways, but I think this is the fastest mathematically proven method.
I hope this helps!

2 Likes