看到高手的線性篩素數方法（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;
}