Check if Number is Prime in DSA Java - Build from Scratch

Check if Number is Prime

📖 Scenario: Imagine you are building a simple tool that helps students learn about prime numbers. A prime number is a number greater than 1 that has no divisors other than 1 and itself.

🎯 Goal: You will create a Java program that checks if a given number is prime or not. This program will help students quickly identify prime numbers.

📋 What You'll Learn

Create an integer variable called number with the value 29

Create a boolean variable called isPrime and set it to true initially

Use a for loop with variable i from 2 to number - 1 to check divisibility

If number is divisible by i, set isPrime to false and break the loop

Print "29 is prime" if isPrime is true, otherwise print "29 is not prime"

💡 Why This Matters

🌍 Real World

Prime number checking is used in cryptography, computer security, and algorithms that require prime numbers.

💼 Career

Understanding prime numbers and loops is fundamental for software developers, especially in fields like security and algorithm design.

1

Create the number variable

Create an integer variable called number and set it to 29.

DSA Java

# Your code here

Hint

Use int number = 29; inside the main method.

2

Create the isPrime variable

Create a boolean variable called isPrime and set it to true inside the main method after number.

DSA Java

public class PrimeCheck {
    public static void main(String[] args) {
        int number = 29;
        // Create isPrime variable here
    }
}

Hint

Use boolean isPrime = true; to start assuming the number is prime.

3

Check divisibility with a for loop

Use a for loop with variable i starting from 2 up to number - 1. Inside the loop, check if number % i == 0. If yes, set isPrime to false and use break to exit the loop.

DSA Java

public class PrimeCheck {
    public static void main(String[] args) {
        int number = 29;
        boolean isPrime = true;
        // Add for loop to check divisibility
    }
}

Hint

Loop from 2 to number-1 and check if number is divisible by i.

4

Print the result

Print "29 is prime" if isPrime is true, otherwise print "29 is not prime".

DSA Java

public class PrimeCheck {
    public static void main(String[] args) {
        int number = 29;
        boolean isPrime = true;
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }
        // Print the result here
    }
}

Hint

Use System.out.println to print the correct message based on isPrime.

Practice

1. What does it mean for a number to be prime?

easy

A. It has exactly two distinct positive divisors: 1 and itself.

B. It is divisible by 2 only.

C. It is an even number greater than 2.

D. It has more than two divisors.

Solution

1. Step 1: Understand the definition of prime number

   A prime number is a number greater than 1 that has no divisors other than 1 and itself.

2. Step 2: Compare options with definition

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states that prime numbers have exactly two distinct positive divisors: 1 and itself.

3. Final Answer:

   It has exactly two distinct positive divisors: 1 and itself. -> Option A

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime numbers have only 1 and itself as divisors [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Assuming 1 is prime

2. Which of the following Java code snippets correctly checks if a number n is prime?

easy

A. for (int i = 2; i < n / 2; i++) { if (n % i == 0) return true; } return false;

B. for (int i = 2; i <= n; i++) { if (n % i == 0) return false; } return true;

C. for (int i = 1; i < n; i++) { if (n % i == 0) return false; } return true;

D. for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true;

Solution

1. Step 1: Analyze the loop range for checking divisors

   We check divisors from 2 up to but not including n to see if n is divisible by any number other than 1 and itself.

2. Step 2: Check each option's logic

   for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; correctly loops from 2 to n-1 and returns false if a divisor is found, else true. for (int i = 2; i <= n; i++) { if (n % i == 0) return false; } return true; incorrectly includes n itself, causing false negatives. for (int i = 1; i < n; i++) { if (n % i == 0) return false; } return true; starts from 1, which divides all numbers. for (int i = 2; i < n / 2; i++) { if (n % i == 0) return true; } return false; returns true on finding a divisor but should return false.

3. Final Answer:

   for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; -> Option D

4. Quick Check:

   Loop 2 to n-1 and check divisibility [OK]

Hint: Loop from 2 to n-1 to check divisors [OK]

Common Mistakes:

• Checking divisibility including n itself
• Starting loop from 1 instead of 2
• Returning true when divisor found

3. What is the output of the following Java code when n = 11?

boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
System.out.println(isPrime);

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand the loop range and condition

   The loop runs from 2 to the square root of 11 (approximately 3.3), so i takes values 2 and 3.

2. Step 2: Check divisibility for i=2 and i=3

   11 % 2 != 0 and 11 % 3 != 0, so no divisor found, isPrime remains true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime, so output is true [OK]

Hint: Check divisors only up to sqrt(n) for efficiency [OK]

Common Mistakes:

• Looping up to n instead of sqrt(n)
• Forgetting to break loop on divisor found
• Misunderstanding boolean flag usage

4. Find the error in the following Java code that checks if n is prime:

boolean isPrime = true;
for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) {
        isPrime = true;
        break;
    }
}
System.out.println(isPrime);

medium

A. The loop should run until i < n, not n / 2.

B. The flag isPrime should be set to false when divisor found, not true.

C. The loop variable i should start from 1, not 2.

D. There is no error; the code works correctly.

Solution

1. Step 1: Analyze the flag update inside the loop

   When a divisor is found, isPrime should be set to false, but here it is incorrectly set to true.

2. Step 2: Check loop range and starting point

   The loop from 2 to n/2 is acceptable for checking divisors, so no error there.

3. Final Answer:

   The flag isPrime should be set to false when divisor found, not true. -> Option B

4. Quick Check:

   Set isPrime = false on divisor found [OK]

Hint: Set prime flag false when divisor found [OK]

Common Mistakes:

• Setting isPrime true inside divisor check
• Looping from 1 instead of 2
• Ignoring break after finding divisor

5. You want to write a Java method isPrime(int n) that returns true if n is prime and false otherwise. Which of the following improvements makes the method more efficient for large n?

hard

A. Check divisibility by all numbers from 2 to n-1 without any break.

B. Check divisibility only by even numbers.

C. Check divisibility only up to the square root of n instead of n-1.

D. Check divisibility by numbers greater than n/2 only.

Solution

1. Step 1: Understand the divisor checking range

   Any divisor larger than the square root of n would have a corresponding divisor smaller than the square root, so checking beyond sqrt(n) is unnecessary.

2. Step 2: Evaluate options for efficiency

   Check divisibility only up to the square root of n instead of n-1. reduces the number of checks drastically, improving efficiency. Check divisibility by all numbers from 2 to n-1 without any break. is inefficient. Check divisibility only by even numbers. is wrong because even numbers except 2 are not prime. Check divisibility by numbers greater than n/2 only. misses smaller divisors.

3. Final Answer:

   Check divisibility only up to the square root of n instead of n-1. -> Option C

4. Quick Check:

   Check divisors up to sqrt(n) for efficiency [OK]

Hint: Only check divisors up to sqrt(n) for speed [OK]

Common Mistakes:

• Checking all numbers up to n-1
• Checking only even numbers
• Ignoring divisor pairs below sqrt(n)