Sieve of Eratosthenes Find All Primes in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the boolean array for marking primes.

DSA Java

boolean[] isPrime = new boolean[[1] + 1];

Drag options to blanks, or click blank then click option'

An

Attempts:

3 left

💡 Hint

Common Mistakes

Using size n instead of n+1 causes index errors.

Forgetting that array indices start at 0.

The array size must be n+1 to include the number n itself.

2fill in blank

medium

Complete the code to mark all numbers as initially prime.

DSA Java

for (int i = 2; i <= [1]; i++) {
    isPrime[i] = true;
}

Drag options to blanks, or click blank then click option'

An

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from 0 or 1.

Looping beyond n.

We mark all numbers from 2 to n as true initially.

3fill in blank

hard

Fix the error in the loop condition to stop at the square root of n.

DSA Java

for (int i = 2; i <= [1]; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

Drag options to blanks, or click blank then click option'

An

B(int) Math.sqrt(n)

Cn / 2

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Looping all the way to n wastes time.

Using n/2 or n-1 is unnecessary.

We only need to check up to the square root of n for efficiency.

4fill in blank

hard

Fill both blanks to print all prime numbers after sieve completion.

DSA Java

for (int i = [1]; i <= [2]; i++) {
    if (isPrime[i]) {
        System.out.print(i + " ");
    }
}

Drag options to blanks, or click blank then click option'

A2

Bn

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 0 or 1 which are not primes.

Stopping before n.

Prime numbers start from 2 up to n.

5fill in blank

hard

Fill all three blanks to complete the Sieve of Eratosthenes method.

DSA Java

public static void sieve(int [1]) {
    boolean[] isPrime = new boolean[[2] + 1];
    for (int i = 2; i <= [3]; i++) {
        isPrime[i] = true;
    }
    for (int i = 2; i <= (int) Math.sqrt([1]); i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= [1]; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= [1]; i++) {
        if (isPrime[i]) {
            System.out.print(i + " ");
        }
    }
}

Drag options to blanks, or click blank then click option'

An

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causing errors.

Incorrect array size or loop limits.

All blanks represent the input number n to define array size, loop limits, and checks.

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