Jun 15, 2025
diff --git a/src/algebra/sieve-of-eratosthenes.md b/src/algebra/sieve-of-eratosthenes.md
 We pre-generate all prime numbers up to $\sqrt R$, and use those primes to mark all composite numbers in the segment $[L, R]$.

 ```cpp
 vector<char>segmentedSieve(long long L, long long R) {
 vector<char>segmented_sieve(long long L, long long R) {
    // generate all primes up to sqrt(R)
    long long lim = sqrt(R);
    vector<char> mark(lim + 1, false);

    vector<char> isPrime(R - L + 1, true);
    for (long long i : primes)
        for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
        for (long long j = max(i, (L + i - 1) / i) * i; j <= R; j += i)
            isPrime[j - L] = false;
    if (L == 1)
        isPrime[0] = false;
    if (L == 0)
        isPrime[L] = false;
    if (L <= 1)
        isPrime[min(1 - L, R - L)] = false;
    return isPrime;
 }
 ```
 It's also possible that we don't pre-generate all prime numbers:

 ```cpp
 vector<char>segmentedSieveNoPreGen(long long L, long long R) {
 vector<char>segmented_sieve_no_pre_gen(long long L, long long R) {
    vector<char> isPrime(R - L + 1, true);
    long long lim = sqrt(R);
    for (long long i = 2; i <= lim; ++i)
        for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
        for (long long j = max(i, (L + i - 1) / i) * i; j <= R; j += i)
            isPrime[j - L] = false;
    if (L == 1)
        isPrime[0] = false;
    if (L == 0)
        isPrime[L] = false;
    if (L <= 1)
        isPrime[min(1 - L, R - L)] = false;
    return isPrime;
 }
 ```

 * [Leetcode - Four Divisors](https://leetcode.com/problems/four-divisors/)
 * [Leetcode - Count Primes](https://leetcode.com/problems/count-primes/)
 * [Leetcode - Closest Prime Numbers in Range](https://leetcode.com/problems/closest-prime-numbers-in-range/)
 * [SPOJ - Printing Some Primes](http://www.spoj.com/problems/TDPRIMES/)
 * [SPOJ - A Conjecture of Paul Erdos](http://www.spoj.com/problems/HS08PAUL/)
 * [SPOJ - Primal Fear](http://www.spoj.com/problems/VECTAR8/)
Original file line number	Diff line number	Diff line change
Expand Up		@@ -207,7 +207,7 @@ To solve such a problem, we can use the idea of the Segmented sieve.
		We pre-generate all prime numbers up to $\sqrt R$, and use those primes to mark all composite numbers in the segment $[L, R]$.

		```cpp
		vector<char>segmentedSieve(long long L, long long R) {
		vector<char>segmented_sieve(long long L, long long R) {
		// generate all primes up to sqrt(R)
		long long lim = sqrt(R);
		vector<char> mark(lim + 1, false);
Expand All		@@ -222,10 +222,12 @@ vector<char> segmentedSieve(long long L, long long R) {

		vector<char> isPrime(R - L + 1, true);
		for (long long i : primes)
		for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
		for (long long j = max(i, (L + i - 1) / i) * i; j <= R; j += i)
		isPrime[j - L] = false;
		if (L == 1)
		isPrime[0] = false;
		if (L == 0)
		isPrime[L] = false;
		if (L <= 1)
		isPrime[min(1 - L, R - L)] = false;
		return isPrime;
		}
		```
Expand All		@@ -234,14 +236,16 @@ Time complexity of this approach is $O((R - L + 1) \log \log (R) + \sqrt R \log
		It's also possible that we don't pre-generate all prime numbers:

		```cpp
		vector<char>segmentedSieveNoPreGen(long long L, long long R) {
		vector<char>segmented_sieve_no_pre_gen(long long L, long long R) {
		vector<char> isPrime(R - L + 1, true);
		long long lim = sqrt(R);
		for (long long i = 2; i <= lim; ++i)
		for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
		for (long long j = max(i, (L + i - 1) / i) * i; j <= R; j += i)
		isPrime[j - L] = false;
		if (L == 1)
		isPrime[0] = false;
		if (L == 0)
		isPrime[L] = false;
		if (L <= 1)
		isPrime[min(1 - L, R - L)] = false;
		return isPrime;
		}
		```
Expand All		@@ -258,6 +262,7 @@ However, this algorithm also has its own weaknesses.

		* [Leetcode - Four Divisors](https://leetcode.com/problems/four-divisors/)
		* [Leetcode - Count Primes](https://leetcode.com/problems/count-primes/)
		* [Leetcode - Closest Prime Numbers in Range](https://leetcode.com/problems/closest-prime-numbers-in-range/)
		* [SPOJ - Printing Some Primes](http://www.spoj.com/problems/TDPRIMES/)
		* [SPOJ - A Conjecture of Paul Erdos](http://www.spoj.com/problems/HS08PAUL/)
		* [SPOJ - Primal Fear](http://www.spoj.com/problems/VECTAR8/)
Expand Down