C ++程序实现分段筛以生成给定范围之间的质数
这是C++程序，用于实现分段筛分以在给定范围之间生成素数。分段筛首先使用简单筛来查找小于或等于√(n)的素数。该算法的思想是将范围[0...n-1]划分为不同的段，并一一计算所有段中的素数。
算法
Begin Create function to find all primes smaller than limit using simple sieve of eratosthenes. Finds all prime numbers in given range using segmented sieve A) Compute all primes smaller or equal to square root of high using simple sieve B) Count of elements in given range C) Declaring boolean only for [low, high] D) Find the minimum number in [low ... high] that is a multiple of prime[i] (divisible by prime[i]) E) Mark multiples of prime[i] in [low … high] F) Numbers which are not marked in range, are prime End
范例程式码
#include <bits/stdc++.h>
using namespace std;
void simpleSieve(int lmt, vector<int>& prime) {
bool mark[lmt + 1];
memset(mark, false, sizeof(mark));
for (int i = 2; i <= lmt; ++i) {
if (mark[i] == false) {
prime.push_back(i);
for (int j = i; j <= lmt; j += i)
mark[j] = true;
}
}
}
void PrimeInRange(int low, int high) {
int lmt = floor(sqrt(high)) + 1;
vector<int> prime;
simpleSieve(lmt, prime);
int n = high - low + 1;
bool mark[n + 1];
memset(mark, false, sizeof(mark));
for (int i = 0; i < prime.size(); i++) {
int lowLim = floor(low / prime[i]) * prime[i];
if (lowLim < low)
lowLim += prime[i];
for (int j = lowLim; j <= high; j += prime[i])
mark[j - low] = true;
}
for (int i = low; i <= high; i++)
if (!mark[i - low])
cout << i << " ";
}
int main() {
int low = 10, high = 50;
PrimeInRange(low, high);
return 0;
}输出结果
11 13 17 19 23 29 31 37 41 43 47
热门推荐
9 年月日祝福语简短
10 班级集体生日祝福语简短
11 祖国七十华诞简短祝福语
12 叔叔生日祝福语简短励志
13 老师祝福语简短100字
14 同事男生节祝福语简短
15 婆婆生日祝福语简短的
16 祝福语怎么写大全简短
17 老师送的祝福语简短
18 很暧昧的简短祝福语