1286.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int prime[4000];
int fri[32768];
int isprime(int n){
    int i,t=sqrt(double(n));
    for(i=2;i<t;i++)
        if(n%i==0)
            return 0;
    return 1;
}
void init(){
    int i,k;
    k=0;
    for(i=2;i<32768;i++)
        if(isprime(i)==1)
            prime[k++]=i;
}
void main()
{
    int num,n,cnt;
    int i,j;
    init();
    cin>>num;
    while(num--){
        memset(fri,0,sizeof(fri));
        cin>>n;
        for(i=0;prime[i]<n;i++)
            if(n%prime[i]==0)
                for(j=prime[i];j<n;j+=prime[i])
                    fri[j]=1;
        cnt=0;
        for(i=1;i<n;i++)
            if(fri[i]==0)
                cnt++;
        cout<<cnt<<endl;
    }
}