Bitwise Sieve ใน C ++

ในปัญหานี้ เราได้รับตัวเลข N หน้าที่ของเราคือค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า N โดยใช้ Bitwise Sieve

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