关注
#include <iostream>
using namespace std;
const int x = 1000001;//使用const是因为能用在下面数组
int a[x];//存答案
bool is_prime[x];//数组内表示是不是质数,是质数为1(真)不是则为0(假)
int main()
{
for(int i = 0;i < x;i++)
is_prime[i] = true;//先把is_prime数组内的值都设为1(真)再使用埃式筛筛出不是质数的数变为0(假)
is_prime[0] = is_prime[1] = false;//0,1不是质数
for(int i = 2;i < x;i++)//埃式筛开始
{
if(is_prime[i])//是质数为真if语句触发
{
for(int j = 2 * i;j < x;j += i)
{
is_prime[j] = false;//筛出不是质数的数都变为0(假)
}
}
}//埃式筛完结
for(int i = 2;i < x;i++)
{
if(is_prime[i])//是质数为真if语句触发
a[i] = a[i - 1] + 1;//统计质数个数方便下面输出
else//表示不是质数
a[i] = a[i - 1];//不是质数质数个数不变
}
int T,n;//题目所给变量
cin >> T;
while(T--)//T--表示个数越来越少直到为0(假)while循环不触发
{
cin >> n;
cout << a[n] << endl;//输出答案
}
return 0;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
709769次浏览 11526人参与
# 许愿池 #
77163次浏览 1541人参与
# 通信硬件人笔面经互助 #
107675次浏览 2177人参与
# 你的秋招进展怎么样了 #
500732次浏览 13422人参与
# 找工作时遇到的神仙HR #
177610次浏览 1744人参与
# 如何写一份好简历 #
259217次浏览 3918人参与
# 铜五铁六真的存在吗? #
27334次浏览 293人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
35030次浏览 352人参与
# 产品实习,你更倾向大公司or小公司 #
35936次浏览 548人参与
# 非技术岗是怎么找实习的 #
73838次浏览 1385人参与
# 市场营销面经 #
4522次浏览 125人参与
# 互联网公司评价 #
79492次浏览 1087人参与
# 通信硬件薪资爆料 #
196229次浏览 1758人参与
# 你的秋招进行到哪一步了 #
352874次浏览 6269人参与
# 硬件兄弟们 甩出你的华为奖状 #
27507次浏览 180人参与
# 无实习如何秋招上岸 #
224596次浏览 3517人参与
# 投了多少份简历才上岸 #
56632次浏览 947人参与
# 面试中的破防瞬间 #
82538次浏览 1015人参与
# 通信/硬件的薪资开多少,才值得去? #
10729次浏览 140人参与
# 产品人求职现状 #
50570次浏览 745人参与