Basic Java Program
A prime number is a positive integer greater than 1 that has no divisors other than 1 and itself. In other words, a prime number can only be divided evenly (without leaving a remainder) by 1 and by the number itself.
Key Points:
- Divisors: A divisor is a number that divides another number completely, without leaving a remainder.
- Greater than 1: The number must be greater than 1. The number 1 is not considered a prime number.
- Exactly Two Divisors: A prime number has exactly two distinct divisors: 1 and itself.
Examples of Prime Numbers:
- 2: The only divisors of 2 are 1 and 2. (2 ÷ 1 = 2, 2 ÷ 2 = 1). So, 2 is a prime number.
- 3: The only divisors of 3 are 1 and 3. (3 ÷ 1 = 3, 3 ÷ 3 = 1). So, 3 is a prime number.
- 5: The only divisors of 5 are 1 and 5. (5 ÷ 1 = 5, 5 ÷ 5 = 1). So, 5 is a prime number.
- 7: The only divisors of 7 are 1 and 7. (7 ÷ 1 = 7, 7 ÷ 7 = 1). So, 7 is a prime number.
The Prime Numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29….
Non-Examples (Not Prime Numbers):
- 4: The divisors of 4 are 1, 2, and 4. Since it has more than two divisors, it’s not a prime number.
- 6: The divisors of 6 are 1, 2, 3, and 6. Since it has more than two divisors, it’s not a prime number.
- 9: The divisors of 9 are 1, 3, and 9. Since it has more than two divisors, it’s not a prime number.
Why Prime Numbers are Important:
- Building Blocks: Prime numbers are like the “building blocks” of all natural numbers. Any number can be expressed as a product of prime numbers (this is called its prime factorization).
- Security: Prime numbers play a crucial role in cryptography, especially in algorithms used for securing online communications.
Thus, a prime number is a number that can only be divided by 1 and itself, making it special and fundamental in mathematics.
import java.util.Scanner;
public class PrimeNumberChecker {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input a number from the user
System.out.print("Enter a number: ");
int number = scanner.nextInt();
// Check if the number is prime
if (isPrime(number)) {
System.out.println(number + " is a prime number.");
} else {
System.out.println(number + " is not a prime number.");
}
scanner.close();
}
// Method to check if a number is prime
public static boolean isPrime(int num) {
// Handle edge cases for numbers less than 2
if (num <= 1) {
return false;
}
// Check for divisibility up to the square root of the number
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false; // If divisible, not a prime number
}
}
return true; // If not divisible by any number, it's a prime number
}
}
// Output:
/* Enter a number:
3
3 is a prime number. */
Explanation
- Input:
- The program prompts the user to input a number.
2. Prime Check:
- The
isPrime
method checks if the number is a prime number. - It handles edge cases where the number is less than or equal to 1, which are not prime numbers.
- The method then checks divisibility by all numbers from
2
up to the square root of the input number (Math.sqrt(num)
). - If the number is divisible by any of these, it’s not a prime number, and the method returns
false
. - If the number is not divisible by any of these, it’s a prime number, and the method returns
true
.
3. Output:
- Based on the result from
isPrime
, the program prints whether the input number is a prime number or not.
Let’s break down the isPrime
method:
public static boolean isPrime(int num) {
- Purpose: This method checks whether the integer
num
is a prime number. - Return Type:
boolean
. It returnstrue
ifnum
is a prime number andfalse
otherwise.
Edge Case Handling
if (num <= 1) {
return false;
}
Explanation: Prime numbers are defined as numbers greater than 1. If num
is less than or equal to 1, it cannot be a prime number, so the method returns false
immediately for such cases.
Divisibility Check
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false; // If divisible, not a prime number
}
}
The for
loop in the code above is designed to check if a number is a prime number by only iterating up to the square root of the number, which makes the process more efficient:
Explanation:
- Initialization:
for (int i = 2; i <= Math.sqrt(num); i++) {
int i = 2;
: The loop starts withi
initialized to 2. We start at 2 because 1 is a divisor for every number and does not help in determining primality (since prime numbers must be greater than 1).i <= Math.sqrt(num);
: The loop continues as long asi
is less than or equal to the square root ofnum
.
2. Checking Divisibility:
if (num % i == 0) {
return false; // If divisible, not a prime number
}
num % i == 0
: This checks ifnum
is divisible byi
without leaving a remainder. Ifnum % i
equals 0, it meansi
is a divisor ofnum
.return false;
: Ifnum
is divisible by any numberi
between 2 andMath.sqrt(num)
, it meansnum
is not a prime number (since it has a divisor other than 1 and itself), and the method returnsfalse
.
Return True
return true;
- After the Loop: If the loop completes and
num
was not found to be divisible by any number from2
tonum / 2
, it meansnum
is not divisible by any number other than 1 and itself. Hence,num
is a prime number, and the method returnstrue
.
In Short,
- The loop checks for divisibility from
2
up to the square root ofnum
. - If
num
is divisible by anyi
in this range, it is not a prime number, and the method returnsfalse
. - If no divisors are found in this range, the number is a prime number, as it was not divisible by any number other than 1 and itself.
- Efficiency: By checking up to
Math.sqrt(num)
, the loop reduces the number of iterations required to determine ifnum
is a prime number. This is because any factor larger thanMath.sqrt(num)
would have a corresponding factor smaller thanMath.sqrt(num)
. This optimization significantly speeds up the primality test, especially for larger numbers.
This method is more efficient than checking up to num / 2
because it reduces the number of divisibility checks required.
Method 2
import java.util.Scanner;
public class PrimeNumber {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number: ");
int number = sc.nextInt();
if(isPrime(number)) {
System.out.println(number + " is a prime number.");
} else {
System.out.println(number + " is not a prime number.");
}
sc.close();
}
public static boolean isPrime(int num) {
// Handle edge cases
if (num <= 1) {
return false;
}
// Check for divisibility from 2 up to num/2
for(int i = 2; i <= num / 2; i++) {
if(num % i == 0) {
return false; // num is divisible by i, so it's not a prime number
}
}
return true; // num is not divisible by any number other than 1 and itself
}
}
Divisibility Check
for(int i = 2; i <= num / 2; i++) {
if(num % i == 0) {
return false;
}
}
Loop: This for
loop checks potential divisors from 2
up to num / 2
.
- Why up to
num / 2
? Checking divisibility beyondnum / 2
is unnecessary because if a numbernum
has a divisor larger thannum / 2
, the other corresponding divisor would be smaller than2
, which we would have already checked.
Condition Inside the Loop:
if(num % i == 0)
: This checks ifnum
is divisible byi
without leaving a remainder. The%
operator returns the remainder of the division.- If
num
is divisible byi
: This meansnum
is not a prime number because it has a divisor other than 1 and itself. So, the method returnsfalse
.
Return True
return true;
- After the Loop: If the loop completes and
num
was not found to be divisible by any number from2
tonum / 2
, it meansnum
is not divisible by any number other than 1 and itself. Hence,num
is a prime number, and the method returnstrue
.
In Short,
- Handle Edge Cases: Return
false
ifnum
is less than or equal to 1. - Check for Divisibility: Use a loop to test all possible divisors from
2
up tonum / 2
.
- If any divisor divides
num
evenly, returnfalse
. - If no divisors are found, return
true
.
This method efficiently determines if a number is prime by checking divisibility only up to half of the number, optimizing performance.