数论基础-欧拉函数

    前几天，在杭电oj上碰到一个数论的题目，附链接： http://acm.hdu.edu.cn/showproblem.php?pid=1286
    题意很简单，就是求一个数N比他小的与它互素（最大公约数为1）的数有多少个。
    刚开始想要暴力的方法去解决这个问题，但后来发现暴力的时间复杂度是O(n^2),而N是32768以内的整数，测试数据有10000组，明显暴力会超时。
    后来教练讲了下，说这种题目要用欧拉函数解决，一个很裸的水题。
    这里介绍下欧拉函数
     Phi（n）=n(1-1/p1) (1-1/p2)….. (1-1/pk)
     其中p1， p2 ，pk是n的所有素数因子
     Phi（n）：所有小于等于n的且与n互素的数的个数
    有了这个定理，这道题的确很容易了（以前没怎么接触数论的题TT）
下面贴代码：

#include<stdio.h>
#include<math.h>
int prime[3600],isprime[32768];
int primeNum;
int findPrime(){
    primeNum = 0;
    for(int i=2;i<32768;i++){
       if(isprime[i]) continue;
       prime[primeNum++] = i;
       for(int j=i*i;j<32768;j+=i)
          isprime[j] = 1;
    }
    return 0;
}
int main(){
    findPrime();
    int t;
    scanf("%d",&t);
    while(t--){
       int n;
       scanf("%d",&n);
       double tmp = n;
       int p = 0;
       while(n!=1){
          if(n%prime[p]==0){
             tmp *=1-1.0/prime[p];
             while(n%prime[p]==0)
                n /= prime[p];
          }
          p++;
       }
       printf("%d\n",(int)round(tmp));
    }
    return 0;
}