資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 位運算篩法
本問題中，我們被賦予一個數字 N。我們的任務是使用位運算篩法找出小於 N 的所有質數。
位運算篩法是埃拉託斯特尼篩法的最佳化版本，用於找出小於給定數字的所有質數。
讓我們舉個例子來理解這個問題：
輸入 − 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
更新日期： 2020 年 8 月 5 日
667 次瀏覽
廣告