函数-素数个数

链接：https://ac.nowcoder.com/acm/contest/93960/J链接：https://ac.nowcoder.com/acm/contest/93960/J

来源：牛客网

对于正整数 n, 求 n 以内的(包括 n)素数个数。

输入描述:

输入第一行为一个正整数 t, 表示一共有 t 组数据，

接下来 t 行，每行一个正整数 n。

输出描述:

输出 t 行，每行一个整数表示 n 以内的素数个数。

#include<iostream>

using namespace std;

bool sushu(int n){

if(n==0||n==1) return false;

if(n==2) return true;

if(n%2==0) return false;

for(int i=3;i*i<=n;i+=2) {

if(n%i==0) return false;

}

return true;

}

int sushucount(int n){

int c=0;

for(int i=2;i<=n;i++) {

if(sushu(i)) {

c++;

}

}

return c;

}

int main()

{

int t;

cin>>t;

int n;

for(int i=0;i<t;i++){

cin>>n;

int c=sushucount(n);

cout<<c<<endl;

}

return 0;

}