Segmented Sieve를 구현하여 주어진 범위 사이의 소수를 생성하는 C++ 프로그램

주어진 범위 사이의 소수를 생성하기 위해 Segmented Sieve를 구현하는 C++ 프로그램입니다. Segmented Sieve는 먼저 Simple Sieve를 사용하여 √(n)보다 작거나 같은 소수를 찾습니다. 이 알고리즘의 아이디어는 범위 [0 ... n-1]을 다른 세그먼트로 나누고 모든 세그먼트의 소수를 하나씩 계산하는 것입니다.

알고리즘

Begin
   Create function to find all primes smaller than limit
   using simple sieve of eratosthenes.
   Finds all prime numbers in given range using
   segmented sieve
   A) Compute all primes smaller or equal to square root of high using simple sieve
   B) Count of elements in given range
   C) Declaring boolean only for [low, high]
   D) Find the minimum number in [low ... high] that is a multiple of prime[i] (divisible by prime[i])
   E) Mark multiples of prime[i] in [low … high]
   F) Numbers which are not marked in range, are prime
End

예시 코드

#include <bits/stdc++.h>
using namespace std;
void simpleSieve(int lmt, vector<int>& prime) {
   bool mark[lmt + 1];
   memset(mark, false, sizeof(mark));
   for (int i = 2; i <= lmt; ++i) {
      if (mark[i] == false) {
         prime.push_back(i);
         for (int j = i; j <= lmt; j += i)
            mark[j] = true;
      }
   }
}
void PrimeInRange(int low, int high) {
   int lmt = floor(sqrt(high)) + 1;
   vector<int> prime;
   simpleSieve(lmt, prime);
   int n = high - low + 1;
   bool mark[n + 1];
   memset(mark, false, sizeof(mark));
   for (int i = 0; i < prime.size(); i++) {
      int lowLim = floor(low / prime[i]) * prime[i];
      if (lowLim < low)
         lowLim += prime[i];
      for (int j = lowLim; j <= high; j += prime[i])
         mark[j - low] = true;
   }
   for (int i = low; i <= high; i++)
      if (!mark[i - low])
         cout << i << " ";
}
int main() {
   int low = 10, high = 50;
   PrimeInRange(low, high);
   return 0;
}

출력

11 13 17 19 23 29 31 37 41 43 47