数据结构
网络
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 次浏览
广告