作法I : 生成組合,集合,排容

首先.先將一個數分解,得到所有的質因數 (不管上面的次方)

例如 : 210 = 2 * 3 * 5 * 7
得到 有 2 3 5 7 這 4 個

答案就是 210- ( (210/2+210/3+210/5+210/7)-(210/6+210/10+210/14+210/15+210/21+210/35) + (210/(2*3*5)+210/(2*3*7)+210/(2*5*7)+210/(3*5*7)) - (210/210) )

一加一減... 需要利用組合

作法II : 數學公式解

我得到了一個尤拉的數學解
你或許有聽過
就是N=A1^B1*A2^B2... (A1是質因數)
那麼答案就是
N*(1-1/A1)*(1-1/A2)...
例如 : 30=2 * 3 * 5
答案=30*(1-1/2)*(1-1/3)*(1-1/5)=30*(1/2)*(2/3)*(4/5)=8

※ 若捨棄掉sqrt() 將會得到意想不到的速度

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int Prime[5200]={0},p; 
char pp[50001]={0};
int n,m;
int prime()  
{  
 int a,b,m=1;
 Prime[0]=2;  
 for(a=3;a<=50000;a=a+2)     
      if(pp[a]==0)     
        {     
           Prime[m]=a;     
           m++;     
           for(b=3;a*b<=50000;b=b+2)     
             pp[a*b]=1;     
        }  
   return m;  
}
int value[51]={0},top;
int Divisors (int num)
{
   int a,b,C=1;
   for(a=0;a<p&&Prime[a]*Prime[a]<=num&&num!=1;a++)
      {
        if(num%Prime[a]==0)
          {
             while(num%Prime[a]==0)
                {
                   num/=Prime[a];
                }
             value[++top]=Prime[a];
          }
      }
    if(num!=1)
      value[++top]=num;
}
int way[51]={0};
int sum;
void make (int now,int a,int n,int m,int s,int div)
{
  int b=a,c;
       if(now%2==0) sum-=div/s;
       else sum+=div/s;
  if(now==m+1)  return;
  else
  for(b=a;b<=n;b++)
   {
    way[now]=b;
    make(now+1,b+1,n,m,s*(value[way[now]]),div);
   }
}
main()
{
 p=prime();
 while(scanf("%d",&n)==1&&n)
    {
     top=0;
     Divisors(n);
     int a;
        sum=0;
     if(top>=1)
        make(1,1,top,top,1,n);
     else sum--;
     printf("%d\n",sum);
    }
 return 0;  
}

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int Prime[3450]={0},p,n; 
char pp[31623]={0};
int prime()  
{  
 int a,b,m=1;
 Prime[0]=2;  
 for(a=3;a<=31622;a=a+2)     
      if(pp[a]==0)     
        {     
           Prime[m]=a;     
           m++;     
           for(b=3;a*b<=31622;b=b+2)     
             pp[a*b]=1;     
        }  
   return m;  
}
int up,down;
int Divisors (int num)
{
   int a,b;
   for(a=0;a<p&&Prime[a]*Prime[a]<=num&&num!=1;a++)
      {
        if(num%Prime[a]==0)
          {
             while(num%Prime[a]==0)
                   num/=Prime[a];
                  
             down/=Prime[a];
             up*=Prime[a]-1;
          }
      }
    if(num!=1)
      {
      down/=num;
      up*=num-1;
      }
}
main()
{
 p=prime();
 while(scanf("%d",&n)==1&&n)
    {
     up=1;down=n;
     Divisors(n);
     if(n!=1)
     printf("%d\n",up*down);
     else printf("0\n");
    }
 return 0;  
}