首页 > Prime
开通博客写题解
头像 东溪看水
发表于 2020-06-16 17:06:14
题目：Prime来源：哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛） 解题思路 在一个闭区间 [a, b] 内，有多少个质数？ 筛法求素数：把从 1 开始的、某一范围内的正整数从小到大顺序排列，1 不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2020-06-15 00:03:14
题解：数据范围式1e7所以感觉尽量还是用一下欧拉筛吧，毕竟时间复杂度越低越好。用visited数组记录，我们用前缀和来处理一下前i个数的质数个数，之后再O(1)的复杂度情况下即可查出。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"O 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”