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 56 57 58
|
#define maxn 100005 #define MOD 1000000007 #define INF 1000000000 using namespace std; typedef long long ll; int prime[maxn], phi[maxn], miu[maxn]; bool is_prime[maxn]; int (int n){ int p = 0; for(int i = 0;i <= n;i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for(int i = 2;i <= n;i++){ if(is_prime[i]) prime[p++] = i; for(int j = 0;j < p;j++){ if(prime[j] * i > n) break; is_prime[prime[j] * i] = false; if(i % prime[j] == 0) break; } } return p; } void genphi(int n){ int p = 0; memset(phi,0,sizeof(phi)); phi[1] = 1; for(int i = 2;i <= n;i++){ if(is_prime[i]) {p++; phi[i] = i - 1;} for(int j = 0;j < p;j++){ if(prime[j] * i > n) break; phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]); if(i % prime[j] == 0) break; } } } void genmiu(int n){ int p = 0; memset(miu,0,sizeof(miu)); miu[1] = 1; for(int i = 2;i <= n;i++){ if(is_prime[i]) {p++; miu[i] = -1;} for(int j = 0;j < p;j++){ if(prime[j] * i > n) break; miu[i * prime[j]] = i % prime[j] ? - miu[i] : 0; if(i % prime[j] == 0) break; } } } int main(){ sieve(100000); genphi(100000); genmiu(100000); for(int i=1;i<=10;i++) printf("%dn",prime[i]); system("pause"); return 0; }
|
近期评论