线性筛求欧拉函数（模板）

关于线性筛的博文：http://www.cnblogs.com/zhuohan123/p/3233011.html

关于欧拉函数的博文：http://www.cnblogs.com/Milkor/p/4471495.html

因为线性筛有大量的取模操作，所以单单使用其筛素数时间可能很慢。但是它有其他更加重要的作用：参考第一篇。

线性筛求欧拉函数：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 #define N 100010
 7 int prime[N], is_prime[N], phi[N];
 8 
 9 // 时间复杂度O(n)
10 // 线性筛求欧拉函数,欧拉函数phi的含义:phi[i]表示1~i里面与i互素的数的数目
11 void Euler(int n) {
12     int cnt = 0;
13     phi[1] = 0;
14     memset(is_prime, 0, sizeof(is_prime));
15     for(int i = 2; i <= n; i++) {
16         if(!is_prime[i]) {
17             prime[++cnt] = i;
18             phi[i] = i - 1;
19         } else {
20             for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
21                 is_prime[i * prime[j]] = 1;
22                 if(i % prime[j] == 0) {
23                     phi[i * prime[j]] = phi[i] * prime[j];
24                     break;
25                 }
26                 phi[i * prime[j]] = phi[i] * phi[prime[j]];
27             }
28         }
29     }
30 }

埃氏筛法：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 100010
 5 int is_prime[N], prime[N];
 6 
 7 // 时间复杂度O(nlognlogn)
 8 void Get_prime(int n) {
 9     memset(is_prime, 0, sizeof(is_prime));
10     int cnt = 0;
11     for(int i = 2; i <= n; i++) {
12         if(is_prime[i]) continue;
13         prime[++cnt] = i;
14         for(int j = 2 * i; j <= n; j += i) is_prime[i] = 1;
15     }
16 }