Prime Generator

Problem

Create a generator that produces primes indefinitely (that is, without taking N as an input).

Examples

Example 1

1
2
3


Input: next() called 5 times
Output: 2, 3, 5, 7, 11
Explanation: The first 5 prime numbers are 2, 3, 5, 7, and 11.

Example 2

1
2
3


Input: next() called 10 times
Output: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Explanation: The first 10 prime numbers are generated in sequence.

Solution

Method 1 – Sieve of Eratosthenes with Dynamic Expansion

Intuition

To generate primes indefinitely, we need a method that can continuously find new primes without knowing the upper bound in advance. The Sieve of Eratosthenes is efficient for finding all primes up to a given limit, but we need to dynamically expand our search space as we need more primes.

Approach

Start with an initial limit (e.g., 100) and use the Sieve of Eratosthenes to find all primes up to that limit.
Maintain an index to track the current position in our list of found primes.
When we exhaust the current list of primes, double the limit and extend the sieve.
Continue yielding primes from our maintained list.
The sieve works by marking all multiples of each prime as composite, leaving only primes unmarked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class PrimeGenerator {
private:
    vector<int> primes;
    int idx;
    int limit;
    
    void sieve(int newLimit) {
        vector<bool> isPrime(newLimit + 1, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= newLimit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= newLimit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        primes.clear();
        for (int i = 2; i <= newLimit; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
        }
        limit = newLimit;
    }
    
public:
    PrimeGenerator() : idx(0), limit(100) {
        sieve(limit);
    }
    
    int next() {
        if (idx >= primes.size()) {
            sieve(limit * 2);
        }
        return primes[idx++];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


type PrimeGenerator struct {
    primes []int
    idx    int
    limit  int
}

func NewPrimeGenerator() *PrimeGenerator {
    pg := &PrimeGenerator{idx: 0, limit: 100}
    pg.sieve(pg.limit)
    return pg
}

func (pg *PrimeGenerator) sieve(newLimit int) {
    isPrime := make([]bool, newLimit+1)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
    
    for i := 2; i*i <= newLimit; i++ {
        if isPrime[i] {
            for j := i * i; j <= newLimit; j += i {
                isPrime[j] = false
            }
        }
    }
    
    pg.primes = pg.primes[:0]
    for i := 2; i <= newLimit; i++ {
        if isPrime[i] {
            pg.primes = append(pg.primes, i)
        }
    }
    pg.limit = newLimit
}

func (pg *PrimeGenerator) Next() int {
    if pg.idx >= len(pg.primes) {
        pg.sieve(pg.limit * 2)
    }
    prime := pg.primes[pg.idx]
    pg.idx++
    return prime
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class PrimeGenerator {
    private List<Integer> primes;
    private int idx;
    private int limit;
    
    public PrimeGenerator() {
        primes = new ArrayList<>();
        idx = 0;
        limit = 100;
        sieve(limit);
    }
    
    private void sieve(int newLimit) {
        boolean[] isPrime = new boolean[newLimit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= newLimit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= newLimit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        primes.clear();
        for (int i = 2; i <= newLimit; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        limit = newLimit;
    }
    
    public int next() {
        if (idx >= primes.size()) {
            sieve(limit * 2);
        }
        return primes.get(idx++);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class PrimeGenerator:
    def __init__(self) -> None:
        self.primes: list[int] = []
        self.idx: int = 0
        self.limit: int = 100
        self._sieve(self.limit)
    
    def _sieve(self, new_limit: int) -> None:
        is_prime = [True] * (new_limit + 1)
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(new_limit**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, new_limit + 1, i):
                    is_prime[j] = False
        
        self.primes = [i for i in range(2, new_limit + 1) if is_prime[i]]
        self.limit = new_limit
    
    def __next__(self) -> int:
        if self.idx >= len(self.primes):
            self._sieve(self.limit * 2)
        prime = self.primes[self.idx]
        self.idx += 1
        return prime
    
    def __iter__(self):
        return self

Complexity

⏰ Time complexity: O(n log log n) for generating primes up to n using Sieve of Eratosthenes, amortized O(1) per prime generated
🧺 Space complexity: O(n) where n is the current limit of the sieve

Method 2 – Trial Division with Optimization

Intuition

An alternative approach is to use trial division to check each number for primality. We can optimize this by only checking divisibility against previously found primes and only up to the square root of the candidate number.

Approach

Start with the first prime (2) and maintain a list of found primes.
For each subsequent number, check if it’s divisible by any of the previously found primes up to its square root.
If no divisor is found, the number is prime.
Add new primes to our list and continue the search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class PrimeGenerator {
private:
    vector<int> primes;
    int candidate;
    
    bool isPrime(int n) {
        for (int p : primes) {
            if (p * p > n) break;
            if (n % p == 0) return false;
        }
        return true;
    }
    
public:
    PrimeGenerator() : candidate(2) {}
    
    int next() {
        if (primes.empty()) {
            primes.push_back(2);
            candidate = 3;
            return 2;
        }
        
        while (!isPrime(candidate)) {
            candidate++;
        }
        
        primes.push_back(candidate);
        int result = candidate;
        candidate++;
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


type PrimeGenerator struct {
    primes    []int
    candidate int
}

func NewPrimeGenerator() *PrimeGenerator {
    return &PrimeGenerator{candidate: 2}
}

func (pg *PrimeGenerator) isPrime(n int) bool {
    for _, p := range pg.primes {
        if p*p > n {
            break
        }
        if n%p == 0 {
            return false
        }
    }
    return true
}

func (pg *PrimeGenerator) Next() int {
    if len(pg.primes) == 0 {
        pg.primes = append(pg.primes, 2)
        pg.candidate = 3
        return 2
    }
    
    for !pg.isPrime(pg.candidate) {
        pg.candidate++
    }
    
    pg.primes = append(pg.primes, pg.candidate)
    result := pg.candidate
    pg.candidate++
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class PrimeGenerator {
    private List<Integer> primes;
    private int candidate;
    
    public PrimeGenerator() {
        primes = new ArrayList<>();
        candidate = 2;
    }
    
    private boolean isPrime(int n) {
        for (int p : primes) {
            if (p * p > n) break;
            if (n % p == 0) return false;
        }
        return true;
    }
    
    public int next() {
        if (primes.isEmpty()) {
            primes.add(2);
            candidate = 3;
            return 2;
        }
        
        while (!isPrime(candidate)) {
            candidate++;
        }
        
        primes.add(candidate);
        int result = candidate;
        candidate++;
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class PrimeGenerator:
    def __init__(self) -> None:
        self.primes: list[int] = []
        self.candidate: int = 2
    
    def _is_prime(self, n: int) -> bool:
        for p in self.primes:
            if p * p > n:
                break
            if n % p == 0:
                return False
        return True
    
    def __next__(self) -> int:
        if not self.primes:
            self.primes.append(2)
            self.candidate = 3
            return 2
        
        while not self._is_prime(self.candidate):
            self.candidate += 1
        
        self.primes.append(self.candidate)
        result = self.candidate
        self.candidate += 1
        return result
    
    def __iter__(self):
        return self

Complexity

⏰ Time complexity: O(n^(3/2) / log n) for generating the first n primes, as each primality test takes O(sqrt(p) / log p) time
🧺 Space complexity: O(n) to store the list of found primes

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 – Sieve of Eratosthenes with Dynamic Expansion#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Trial Division with Optimization#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 – Sieve of Eratosthenes with Dynamic Expansion

Intuition

Approach

Code

Complexity

Method 2 – Trial Division with Optimization

Intuition

Approach

Code

Complexity