이 문제에서는 숫자 N이 주어집니다. 우리의 임무는 Bitwise Sieve를 사용하여 N보다 작은 모든 소수를 찾는 것입니다.
Bitwise sieve는 주어진 숫자보다 작은 모든 소수를 찾는 데 사용되는 Sieve of Eratosthenes의 최적화된 버전입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - N =25
출력 − 2 3 5 7 11 13 17 19 23
비트 체는 일반 체와 동일한 방식으로 작동합니다. 부울 유형 대신 소수를 나타내는 정수 비트를 사용합니다. 이렇게 하면 공간 복잡성이 1/8로 줄어듭니다.
예시
솔루션을 이해하기 위해 코드를 살펴보겠습니다.
#include <iostream> #include <math.h> #include <cstring> using namespace std; bool ifnotPrime(int prime[], int x) { return (prime[x/64]&(1<<((x>>1)&31))); } bool makeComposite(int prime[], int x) { prime[x/64]|=(1<<((x>>1)&31)); } void bitWiseSieve(int n){ int prime[n/64]; memset(prime, 0, sizeof(prime)); for (int i = 3; i<= sqrt(n); i= i+2) { if (!ifnotPrime(prime, i)) for (int j=pow(i,2), k= i<<1; j<n; j+=k) makeComposite(prime, j); } for (int i = 3; i <= n; i += 2) if (!ifnotPrime(prime, i)) printf("%d\t", i); } int main(){ int N = 37; printf("All the prime number less than %d are 2\t", N); bitWiseSieve(N); return 0; }
출력
All the prime number less than 37 are 2 3 5 7 11 13 17 19 23 29 31 37