Sieve of Eratosthenes Find All Primes in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Sieve of Eratosthenes?

It is a method to find all prime numbers up to a given limit by repeatedly marking the multiples of each prime number starting from 2.

intermediate

Why do we start marking multiples from the square of the current prime in the Sieve of Eratosthenes?

Because all smaller multiples of the prime have already been marked by smaller primes, so starting from the square avoids redundant work.

beginner

In the Sieve of Eratosthenes, what data structure is commonly used to keep track of prime candidates?

A boolean array where each index represents a number; true means the number is still considered prime, false means it is marked as not prime.

intermediate

What is the time complexity of the Sieve of Eratosthenes algorithm?

The time complexity is O(n log log n), which is very efficient for finding primes up to n.

beginner

How does the Sieve of Eratosthenes differ from checking primality by trial division?

The sieve finds all primes up to n at once by marking multiples, while trial division checks each number individually by dividing it by smaller numbers.

What number do we start marking multiples from in the Sieve of Eratosthenes for a prime p?

A 1

B 2 * p

C p + 1

D p * p

We start marking multiples from p squared because smaller multiples have already been marked by smaller primes.

What does a 'false' value in the sieve's boolean array represent?

A The number is not prime

B The number is 1

C The number is unknown

D The number is prime

False means the number has been marked as not prime (a multiple of some prime).

Which of these is the correct time complexity of the Sieve of Eratosthenes?

A O(n log n)

B O(n log log n)

C O(n^2)

D O(log n)

The sieve runs in O(n log log n) time, which is efficient for large n.

Why is the Sieve of Eratosthenes efficient for finding all primes up to n?

A It checks each number individually

B It uses recursion

C It marks multiples of primes only once

D It sorts the numbers first

The sieve marks multiples of each prime only once, avoiding repeated work.

What is the first prime number used in the Sieve of Eratosthenes?

A 2

B 1

C 0

D 3

2 is the smallest prime number and the starting point for the sieve.

Explain how the Sieve of Eratosthenes finds all prime numbers up to a given number n.

Think about crossing out multiples step by step.

Describe why the Sieve of Eratosthenes is more efficient than checking each number's primality by trial division.

Focus on how the sieve reduces repeated work.

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