Bitwise Sieve trong C ++

Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là tìm tất cả các số nguyên tố nhỏ hơn N bằng cách sử dụng Bitwise Sieve.

Bitwise sieve là một phiên bản được tối ưu hóa của Sieve of Eratosthenes được sử dụng để tìm tất cả các số nguyên tố nhỏ hơn một số đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - N =25

Đầu ra - 2 3 5 7 11 13 17 19 23

Rây bitwise hoạt động theo các cách tương tự như sàng bình thường. Nó chỉ là chúng ta sẽ sử dụng các bit của số nguyên đại diện cho số nguyên tố thay vì kiểu boolean. Điều này sẽ làm giảm độ phức tạp của không gian xuống 1/8 lần.

Ví dụ

Hãy xem mã để hiểu giải pháp,

#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;
}

Đầu ra

All the prime number less than 37 are 2 3 5 7 11 13 17 19 23 29 31 37