看到高手的线性筛素数方法（Prime2函数)：
const int N = 25600000;
bool a[N];
int p[N];
int n;
void Prime1() {
memset(a, 0, n * sizeof(a[0]));
int num = 0, i, j;
for(i = 2; i < n; ++i) if(!a[i]) {
p[num++] = i;
for(j = i+i; j < n; j +=i) {
a[j] = 1;
}
}
}
void Prime2() {
memset(a, 0, n*sizeof(a[0]));
int num = 0, i, j;
for(i = 2; i < n; ++i) {
if(!(a[i])) p[num++] = i;
for(j = 0; (j<num && i*p[j]<n); ++j) {
a[i*p[j]] = 1;
if(!(i%p[j])) break;
}
}
}
测试:
筛 [0, 100000) 范围内的素数
第一种素数筛法 0 毫秒
第二种素数筛法 0 毫秒
筛 [0, 200000) 范围内的素数
第一种素数筛法 15 毫秒
第二种素数筛法 0 毫秒
筛 [0, 400000) 范围内的素数
第一种素数筛法 16 毫秒
第二种素数筛法 15 毫秒
筛 [0, 800000) 范围内的素数
第一种素数筛法 47 毫秒
第二种素数筛法 16 毫秒
筛 [0, 1600000) 范围内的素数
第一种素数筛法 62 毫秒
第二种素数筛法 63 毫秒
筛 [0, 3200000) 范围内的素数
第一种素数筛法 297 毫秒
第二种素数筛法 109 毫秒
筛 [0, 6400000) 范围内的素数
第一种素数筛法 922 毫秒
第二种素数筛法 266 毫秒
筛 [0, 12800000) 范围内的素数
第一种素数筛法 2187 毫秒
第二种素数筛法 563 毫秒
筛 [0, 25600000) 范围内的素数
第一种素数筛法 4828 毫秒
第二种素数筛法 1187 毫秒
证明：任何一个合数只被标记一次。
可以试着执行下这个程序的流程，就明白了
怎么样 还行吧？
什么，觉得这个程序效率上没多大提升，没有什么用？
把a[]改成int类型，然后
void Prime2() {
memset(a, 0, n*sizeof(a[0]));
int num = 0, i, j;
for(i = 2; i < n; ++i) {
if(!(a[i])) p[num++] = i;
for(j = 0; (j<num && i*p[j]<n && (p[j]<=a[i]||a[i]==0)); ++j) {
a[i*p[j]] = p[j];
}
}
}
这样一来a[i]将记录i的最小质因子
那么[0, n)内的数的因式分解就可以... 嘿嘿
o(质因子个数)求任意数因式分解：
void factor(int x) {
while(a[x] != 0) {
printf("%d\n", a[x]);
x /= a[x];
}
printf("%d\n", x);
}
然后用这个做了上次杭州比赛的GCD那题，虽然其实就是个容斥原理，可是我等白菜就是不会做。唉。
第一名8题，我们4题，这个差距大的有点想吐。
题目
http://acm.hdu.edu.cn/showproblem.php?pid=1695
//Solution by alpc12:
#include <string.h>
#include <stdio.h>
const int N = 100010;
typedef __int64 LL;
#define I64Format "%I64d\n"
inline int count(int x) {int ret = 0;while(x != 0) {ret ++; x &= (x-1);}return ret;}
int a[N], p[18000];
void pre() {
memset(a, 0, sizeof(a));
int num = 0, i, j;
for(i = 2; i < N; ++i) {
if(!a[i]) p[num++] = i;
for(j = 0; j < num && i * p[j] < N && (p[j]<=a[i] || a[i]==0); ++j) {
a[p[j] * i] = p[j];
}
}
}
void go(int x, int y) {
if(x == 0) { printf("0\n"); return; }
int i, j;
LL ans = 0;
for(i = 1; i <= y; ++i) {
if(!a[i]) {
ans += (i<=x?(i-1):x);
} else {
int fac[20], nfac = 0, z = i;
while(a[z] != 0) {
fac[nfac++] = a[z];
z /= a[z];
}
fac[nfac++] = z;
int k = 1;
for(j = 1; j < nfac; ++j) {
if(fac[j] != fac[j-1])
fac[k++] = fac[j];
}
nfac = k;
int now = 0;
int xx = x;
if(x >= i) xx=i-1;
int mask;
for(mask = 1; mask < (1<<nfac); ++mask) {
int d = count(mask), mul = 1;
for(j = 0; j < nfac; ++j) if((mask&(1<<j)) != 0) {
mul *= fac[j];
}
if(d&1) now += xx/mul;
else now -= xx/mul;
}
ans += xx-now;
}
}
printf(I64Format, 1+ans);
}
int main() {
// freopen("t.in", "r", stdin);
int ntc, a, b, c, d, k;
scanf("%d", &ntc);
pre();
int tc = 0;
while(ntc--) {
printf("Case %d: ", ++tc);
scanf(" %d %d %d %d %d", &a, &b, &c, &d, &k);
if(k == 0) printf("0\n");
else {
a = b/k;
b = d/k;
if(a > b) go(b, a);
else go(a, b);
}
}
return 0;
}