Sieve of Eratosthenes Find All Primes in DSA Java - Build from Scratch

Sieve of Eratosthenes Find All Primes

📖 Scenario: You are helping a teacher prepare a list of prime numbers for a math class. The teacher wants to find all prime numbers up to a certain number using a fast method called the Sieve of Eratosthenes.

🎯 Goal: Build a Java program that uses the Sieve of Eratosthenes to find and print all prime numbers up to 30.

📋 What You'll Learn

Create a boolean array to mark prime numbers

Use a variable to set the maximum number (30)

Implement the sieve algorithm to mark non-primes

Print all prime numbers found

💡 Why This Matters

🌍 Real World

Finding prime numbers is important in cryptography, computer security, and mathematical research.

💼 Career

Understanding prime number algorithms helps in software development roles involving security, algorithms, and performance optimization.

1

Create the boolean array for primes

Create a boolean array called isPrime of size 31 to represent numbers from 0 to 30. Initialize all values to true except for isPrime[0] and isPrime[1], which should be false.

DSA Java

// Create the boolean array isPrime with size 31
// Set isPrime[0] and isPrime[1] to false
// Set all other values to true

Hint

Remember, 0 and 1 are not prime numbers, so mark them as false. Use a loop to set the rest to true.

2

Set the maximum number variable

Add an integer variable called max and set it to 30. This will be the highest number to check for primes.

DSA Java

public class Sieve {
    public static void main(String[] args) {
        boolean[] isPrime = new boolean[31];
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        // Create an int variable max and set it to 30
    }
}

Hint

This variable will help control the range of numbers to check.

3

Implement the sieve algorithm

Use a for loop with variable i from 2 to Math.sqrt(max) (cast to int). Inside it, use another for loop with variable j starting from i * i to max, incrementing by i. Inside the inner loop, set isPrime[j] to false.

DSA Java

public class Sieve {
    public static void main(String[] args) {
        boolean[] isPrime = new boolean[31];
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        int max = 30;
        // Add the sieve algorithm loops here
    }
}

Hint

Mark multiples of each prime number as not prime.

4

Print all prime numbers

Use a for loop with variable i from 2 to max. Inside the loop, if isPrime[i] is true, print i followed by a space. After the loop, print a new line.

DSA Java

public class Sieve {
    public static void main(String[] args) {
        boolean[] isPrime = new boolean[31];
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        int max = 30;
        for (int i = 2; i <= (int) Math.sqrt(max); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // Print all prime numbers from 2 to max
    }
}

Hint

Print each prime number followed by a space, then print a new line after all primes.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To find all prime numbers up to a given limit

B. To sort an array of numbers

C. To find the greatest common divisor of two numbers

D. To reverse a string

Solution

1. Step 1: Understand the algorithm's goal

   The Sieve of Eratosthenes is designed to identify prime numbers efficiently.

2. Step 2: Recognize the output

   It marks multiples of primes as non-prime, leaving primes unmarked up to a limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option A

4. Quick Check:

   Prime finding = To find all prime numbers up to a given limit [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing with sorting algorithms
• Thinking it finds divisors
• Assuming it manipulates strings

2. Which of the following Java code snippets correctly initializes the boolean array for the sieve to find primes up to n?

easy

A. boolean[] prime = new boolean[n+1]; Arrays.fill(prime, false);

B. boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true);

C. boolean[] prime = new boolean[n]; Arrays.fill(prime, false);

D. boolean[] prime = new boolean[n]; Arrays.fill(prime, true);

Solution

1. Step 1: Check array size for indexing

   We need size n+1 to include number n as index.

2. Step 2: Initialize all as true

   All numbers start as prime candidates, so fill with true.

3. Final Answer:

   boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); -> Option B

4. Quick Check:

   Array size n+1 and true fill = boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); [OK]

Hint: Use n+1 size and fill true for sieve array [OK]

Common Mistakes:

• Using size n instead of n+1
• Filling array with false initially
• Confusing array size and indexing

3. What will be the output list of primes printed by the following Java code snippet for n = 10?

int n = 10;
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false; prime[1] = false;
for (int p = 2; p * p <= n; p++) {
  if (prime[p]) {
    for (int i = p * p; i <= n; i += p) {
      prime[i] = false;
    }
  }
}
for (int i = 2; i <= n; i++) {
  if (prime[i]) System.out.print(i + " ");
}

medium

A. 2 3 5 7

B. 2 3 4 5 7

C. 1 2 3 5 7

D. 2 3 5 7 9

Solution

1. Step 1: Initialize primes and mark 0,1 false

   prime[0] and prime[1] are false; others true initially.

2. Step 2: Mark multiples of primes false

   Multiples of 2 (4,6,8,10) and 3 (9) are marked false.

3. Step 3: Print primes from 2 to 10

   Remaining true indices are 2,3,5,7.

4. Final Answer:

   2 3 5 7 -> Option A

5. Quick Check:

   Primes up to 10 = 2 3 5 7 [OK]

Hint: Mark multiples starting from p*p to optimize [OK]

Common Mistakes:

• Including 1 as prime
• Printing non-prime numbers like 4 or 9
• Not starting inner loop from p*p

4. Identify the error in the following Java code snippet implementing the Sieve of Eratosthenes:

int n = 20;
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = false; prime[1] = false;
for (int p = 2; p <= n; p++) {
  if (prime[p]) {
    for (int i = p * 2; i <= n; i += p) {
      prime[i] = false;
    }
  }
}

medium

A. Arrays.fill should initialize with false, not true

B. The inner loop should start from p, not p*2

C. The outer loop should run only up to sqrt(n), not n

D. prime[0] and prime[1] should be true

Solution

1. Step 1: Check outer loop range

   Outer loop runs from 2 to n, but it is enough to run up to sqrt(n) for efficiency.

2. Step 2: Confirm inner loop start and initialization

   Inner loop correctly starts at p*2; prime[0] and prime[1] are correctly false; array filled with true.

3. Final Answer:

   The outer loop should run only up to sqrt(n), not n -> Option C

4. Quick Check:

   Loop limit optimization = The outer loop should run only up to sqrt(n), not n [OK]

Hint: Outer loop limit is sqrt(n) for efficiency [OK]

Common Mistakes:

• Running outer loop up to n wastes time
• Starting inner loop incorrectly
• Wrong initialization of prime array

5. You want to find all prime numbers up to n = 50 using the Sieve of Eratosthenes. After running the sieve, how many prime numbers will be found?

hard

A. 13

B. 16

C. 14

D. 15

Solution

1. Step 1: List primes up to 50

   Primes are 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (total 15).

2. Step 2: Count primes carefully

   Counting again: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 = 15 primes.

3. Step 3: Verify options

   15 says 15, 16 says 16; correct count is 15.

4. Final Answer:

   15 -> Option D

5. Quick Check:

   Count primes ≤ 50 = 15 [OK]

Hint: Memorize primes or count after sieve [OK]

Common Mistakes:

• Counting 1 as prime
• Miscounting primes between 40 and 50
• Assuming 16 primes instead of 15