I want to be CRAZY!!!
本来无望的事，大胆尝试，往往能成功。
筛素数和欧拉函数的模板
筛素数和欧拉函数
/*
******************************************************************************
素数＋欧拉函数表
******************************************************************************
*/
const
int
size = 1000010;
int
phi[size], prime[size];
bool
check[size];
void
excelphi() {
memset(check,
false
,
sizeof
(check));
phi[1] = 1;
int
tot = 0;
for
(
int
i = 2; i <= size; i++) {
if
(!check[i]) {
prime[tot++] = i;
phi[i] = i - 1;
}
for
(
int
j = 0; j < tot; j++) {
if
(i * prime[j] > size)
break
;
check[i*prime[j]] =
true
;
if
(i % prime[j] == 0) {
phi[i*prime[j]] = phi[i]*prime[j];
break
;
}
else
{
phi[i*prime[j]] = phi[i]*(prime[j] - 1);
}
}
}
}
再贴个筛区间素数的：
筛区间素数
/*
******************************************************************************
筛区间素数
******************************************************************************
*/
const
int
size = 32000, maxn = 1000010;
int
check[maxn], prime[size], ans[maxn], cnt;
void
get_small_prime() {
cnt = 0;
memset(check, 0,
sizeof
(check));
for
(
int
i = 2; i < size; i++) {
if
(!check[i]) prime[cnt++] = i;
for
(
int
j = i * i; j < size; j += i)
check[i] = 1;
}
}
void
get_large_prime(
int
l,
int
r) {
cnt = 0;
memset(ans, 0,
sizeof
(ans));
memset(check, 0,
sizeof
(check));
for
(
int
i = 0; prime[i] * prime[i] <= r; i++)
for
(
int
j = l / prime[i]; j * prime[i] <= r; j++)
if
(j > 1 && j * prime[i] >= l)
check[j * prime[i] - l] = 1;
for
(
int
i = l; i <= r; i++)
if
(!check[i-l] && i > 1)
ans[cnt++] = i;
}
posted on 2012-09-17 18:23
phonism
阅读(210)
评论(0)
编辑
收藏
引用
所属分类:
数学
只有注册用户
登录
后才能发表评论。
相关文章:
几道GCD相关题目总结
DP求期望入门
筛素数和欧拉函数的模板
Matrix小记
网站导航:
博客园
博客园最新博文
博问
管理
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2012年8月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
统计
随笔 - 7
文章 - 0
评论 - 0
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
比赛
(rss)
动态规划(3)
(rss)
感想(1)
(rss)
数据结构
(rss)
数学(4)
(rss)
图论
(rss)
杂乱(2)
(rss)
随笔档案
2012年9月 (3)
2012年8月 (4)
搜索
最新评论
阅读排行榜
1. 背包小记(369)
2. Matrix小记(296)
3. 几道GCD相关题目总结(275)
4. DP求期望入门(263)
5. 2012.8.3日水一发(260)
评论排行榜
1. 几道GCD相关题目总结(0)
2. DP求期望入门(0)
3. 筛素数和欧拉函数的模板(0)
4. 浅尝状态压缩(0)
5. Matrix小记(0)