|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 |
/*** 求LCM(1,2,3,...n)**/#include <iostream>#include <cstdio>#include <algorithm>using
namespace std;#define N 100000010unsigned int
prime[6000000], p[6000000], T, num;unsigned int
flag[3126000];void
slove(int
n) { unsigned int
res = 1; int
i, t1, t2; for(i = 0; i <= num && prime[i] * prime[i] <= n; ++i) { t1 = prime[i]; t2 = prime[i] * prime[i]; while(t2 / t1 == prime[i] && t2 <= n) { t1 *= prime[i]; t2 *= prime[i]; } res *= (t1 / prime[i]); } int
t = upper_bound(prime, prime+num, n) - prime - 1; res *= p[t]; printf("%u\n", res);}//生成素数void
initPrime() { int
i, j; p[num=0] = prime[0] = 2; for(i = 3; i < N; i += 2) { if( !(flag[i/32]&(1<<(i%32))) ) { prime[++num] = i; p[num] = i * p[num-1]; for(j = i * 3; j < N; j += i * 2) flag[j/32] |= 1<<(j%32); } }}int
main() { initPrime(); prime[++num] = 100000003; scanf("%d", &T);; int
i, n; for(i = 0; i < T; ++i) { scanf("%d", &n); slove(n); } return
0;} |
原文：http://www.cnblogs.com/yaling/p/3572290.html