1286 找新朋友.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1286 找新朋友
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

671 MS 344 KB 851 B
GUN C++
*/
#include <iostream>
using namespace std;

const int Max=32768;

int Factor(int save[],int num)
{
    int now;
    int i,pre;

    now=0;
    i=2;pre=0;
    while(num>1)
    {
        if(num%i==0)
        {
            num/=i;
            if(i!=pre)
            {   save[now]=i;now++;pre=i;}
        }
        else
            i++;
    }
    return now;
}

int main()
{
    int t,n,i,j,k;
    int fac[100]={0},size;

    cin>>t;
    while(t--)
    {
        cin>>n;
        size=Factor(fac,n);
        k=0;
        
        for(i=1;i<n;i++)
        {
            j=0;
            while(j<size)
                if(i%fac[j]==0)
                    break;
                else
                    j++;
            if(j==size)
                k++;
        }

        cout<<k<<endl;
    }
    return 0;
}