#include<cstring>
using namespace std;
bool vis[1000000]; //存储某个数(下标)是不是素数,是则为true,否则为false
int prime[1000000]; //存储前n个素数,注意不是不超过n的素数,是前n 个。
void init_prim() {
memset(vis, true, sizeof(vis));
vis[0] = vis[1] = false; //0和1不是素数
int num = 0;
for (int i = 2; i <= n; ++i) {
if (vis[i] == true) {
num++;
prime[num] = i;
}
for (int j = 1; ((j <= num) && (i * prime[j] <= n)); ++j) {
vis[i * prime[j]] = false;
if (i % prime[j] == 0)
break; //点睛之笔
}
}
}
相关文章
- 04-13素数打表法
- 04-13GCD + LCM + 素数打表 + 快速幂
- 04-13数据结构-线性表-课后题13一个线性表(a1,a2,···,an)(n>3)采用带头结点的单链表L存储,设计一个高效算法求中间位置的元素(即序号为[n/2]的元素)。
- 04-13HDU 1397 Goldbach's Conjecture(素数打表)
- 04-13light1236 素数打表,质因数分解
- 04-13hdu 1431 素数回文(暴力打表,埃托色尼筛法)
- 04-13C#7.2——编写安全高效的C#代码 c# 中模拟一个模式匹配及匹配值抽取 走进 LINQ 的世界 移除Excel工作表密码保护小工具含C#源代码 腾讯QQ会员中心g_tk32算法【C#版】
- 04-13【算法系列学习三】[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 反向bfs打表和康拓展开
- 04-13ACM/ICPC 之 数论-素数筛选法 与 "打表"思路(POJ 1595)
- 04-13POJ——3126Prime Path(双向BFS+素数筛打表)