C ++中的按位筛选
在这个问题中，给我们一个数字N。我们的任务是使用按位筛选找到所有小于N的素数。
按位筛是Eratosthenes筛的优化版本，用于查找所有小于给定数的素数。
让我们举个例子来了解这个问题，
输入-N=25
输出-23571113171923
按位筛子的工作方式与普通筛子相同。只是我们将使用表示素数的整数位而不是布尔类型。这样可以将空间复杂度降低到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
热门推荐
10 老同学十一祝福语简短
11 上级买车祝福语大全简短
12 送给情侣贺卡祝福语简短
13 虎年伊始祝福语大全简短
14 阳历新年祝福语大全 简短
15 同事们生日祝福语简短
16 家庭恩爱祝福语大全简短
17 项目总生日祝福语简短
18 毕业结婚祝福语简短精辟