Hdu 1286 找新朋友

开始题目看错了，以为是求老朋友的个数，后来发现题目要求求新朋友的个数。筛选法。。。

CODE：

   #include <stdio.h>
   
#include <stdlib.h>
   
#include <math.h>
   
#include <
   string.h>
   

   using 
   namespace std;
   

   

   const 
   int maxn = 
   32769;
   

   int vis[maxn] = {
   0};
   

   int N, cnt;
   

   

   void init(
   int n, 
   int& cnt)
   
{
   
    
   int i, j;
   
    cnt = 
   0;
   
    memset(vis, 
   0, 
   sizeof(vis));
   
    
   for(i = 
   2 ; i < n; i++) 
   if(!vis[i])
   
    {
   
        
   if(n%i == 
   0)
   
        {
   
            
   for(j = i; j < n; j+=i) vis[j]++;        
   //不是从i*i开始
   
        }
   
    }
   
    
   for(i = 
   1 ; i < n ;i++) 
   if(!vis[i])
   
    {
   
        cnt++;
   
    }
   
    
   return ;
   
}
   

   

   

   int main()
   
{
   
    
   int T;
   
    scanf(
   "
   %d
   ", &T);
   
    
   while(T--)
   
    {
   
        scanf(
   "
   %d
   ", &N);
   
        init(N, cnt);
   
        printf(
   "
   %d\n
   ", cnt);
   
    }
   
    
   return 
   0;
  

}