数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法学C++ 程序通过实施阿特金筛法生成指定范围内的质数
这是 C++ 程序，通过实施阿特金筛法生成指定范围内的质数。阿特金筛法是一种现代算法，用于找出指定整数中的所有质数。
算法
Begin Create a results list, filled with 2, 3, and 5. Initialize the sieve array with false values Mark siev[n] is true if one of the following is true: a) n = (4*x*x) + (y*y) has odd number of solutions n % 12 = 1 or n % 12 = 5. b) n = (3*x*x) + (y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x) - (y*y) has odd number of solutions, x > y and n % 12 = 11 Mark all multiples of squares as non-prime Print primes using sieve[] End
示例代码
#include <bits/stdc++.h>
using namespace std;
int SieveOfAtkin(int lmt) {
if (lmt > 2)
cout << 2 << " ";
if (lmt > 3)
cout << 3 << " ";
bool sieve[lmt];
for (int i = 0; i < lmt; i++)
sieve[i] = false;
for (int a = 1; a * a < lmt; a++) {
for (int b = 1; b * b < lmt; b++) {
// Main part of Sieve of Atkin
int n = (4 * a* a) + (b * b);
if (n <= lmt && (n % 12 == 1 || n % 12 == 5))
sieve[n] ^= true;
n = (3 * a * a) + (b * b);
if (n <= lmt && n % 12 == 7)
sieve[n] ^= true;
n = (3 * a * a) - (b * b);
if (a > b && n <= lmt && n % 12 == 11)
sieve[n] ^= true;
}
}
for (int r = 5; r * r < lmt; r++) {
if (sieve[r]) {
for (int i = r * r; i < lmt; i += r * r)
sieve[i] = false;
}
}
for (int x = 5; x < lmt; x++)
if (sieve[x])
cout << x << " ";
}
int main(void) {
int lmt = 30;
SieveOfAtkin(lmt);
return 0;
}输出
2 3 5 7 11 13 17 19 23 29
更新于:2019 年 7 月 30 日
412 次浏览
广告