数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2019 年 7 月 30 日
870 次浏览
广告