[素数]线性筛-欧拉函数

佚名 6年前 (2019-04-26) 随笔 1596人围观抢沙发百度已收录

 1 int tot = 0;
 2 memset(check, 0, sizeof(check));
 3 for (int i = 2; i < MAXL; ++i)
 4 {
 5   if (!check[i])
 6   {
 7     prime[tot++] = i;
 8   }
 9   for (int j = 0; j < tot; ++j)
10   {
11     if (i * prime[j] > MAXL)
12     {
13       break;
14     }
15     check[i*prime[j]] = 1;
16     if (i % prime[j] == 0)
17     {
18       break;
19     }
20   }
21 }

欧拉函数：在数论，对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 100005
 4 #define MAXL 1299710
 5 int prime[MAXN];
 6 int check[MAXL];
 7 int phi[MAXL];
 8 int tot = 0;
 9 phi[1] = 1;
10 memset(check, 0, sizeof(check));
11 for (int i = 2; i < MAXL; ++i)
12 {
13   if (!check[i])
14   {
15     prime[tot++] = i;
16     phi[i] = i - 1;
17   }
18   for (int j = 0; j < tot; ++j)
19   {
20     if (i * prime[j] > MAXL)
21     {
22       break;
23     }
24     check[i*prime[j]] = 1;
25     if (i % prime[j] == 0)
26     {
27       phi[i*prime[j]] = phi[i] * prime[j];
28       break;
29     }else
30     {
31       phi[i*prime[j]] = phi[i] * (prime[j]-1);
32     }
33   }
34 }