题目链接 POJ2407 This is the link
Problem Description
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
7 12 0
Sample Output
6 4
题目要求：计算1-n中与n互质的数有多少？
表示不能用线性筛素数的方法，（时间和空间都会爆）所以有了下面的方法
欧拉函数的性质：
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
当m是素数时φ(m)=m-1;
This is the code
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<iostream>#include <iomanip>#include<list>#include<queue>#include<sstream>#include<stack>#include<string>#include<set>#include<vector>using namespace std;#define PI acos(-1.0)#define EPS 1e-8#define MOD 1e9+7#define LL long long#define ULL unsigned long long //1844674407370955161#define INT_INF 0x7f7f7f7f //2139062143#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};// ios.sync_with_stdio(false);// 那么cin, 就不能跟C的scanf,sscanf,getchar,fgets之类的一起使用了。const int N=100000000;int phi[N+5];bool v[N+5];int Phi(int n){ int ret=1; for(int i=2;i*i<=n;++i) { if(!(n%i)) { n/=i; ret*=(i-1); while(!(n%i)) { n/=i; ret*=i; } } } if(n>1) ret*=(n-1); return ret;}int main(){ int n; while(scanf("%d",&n)!=EOF) { if(!n) break; int ans=Phi(n); printf("%dn",ans); } return 0;}