您现在的位置是：主页 > news > wordpress免费网站模板/白帽seo
wordpress免费网站模板/白帽seo
admin2025/6/29 9:37:08【news】
简介wordpress免费网站模板,白帽seo,新闻网站诚信建设工作总结,网站更换主机3.6 素数筛选有的时候，题目要求我们筛选出一段区间内的素数，我们就需要掌握一种素数筛选的方法。如果用上一节素数判定的方法去判定每一个数是不是素数的话。复杂度是O(n*sqrt(n))，大概能处理到10000以内的数。如果题目要求的范围更大&#x…
wordpress免费网站模板,白帽seo,新闻网站诚信建设工作总结,网站更换主机3.6 素数筛选有的时候，题目要求我们筛选出一段区间内的素数，我们就需要掌握一种素数筛选的方法。如果用上一节素数判定的方法去判定每一个数是不是素数的话。复杂度是O(n*sqrt(n))，大概能处理到10000以内的数。如果题目要求的范围更大&#x…
3.6 素数筛选
有的时候，题目要求我们筛选出一段区间内的素数，我们就需要掌握一种素数筛选的方法。
如果用上一节素数判定的方法去判定每一个数是不是素数的话。
复杂度是O(n*sqrt(n))，大概能处理到10000以内的数。
如果题目要求的范围更大，那么我们就需要一种更为高效的筛选法。
掌握下面这一种线性复杂度的筛选方法就足够我们应对任何情况。
1. // 线性素数筛选 prime[0]存的是素数的个数
2. const int maxn = 1000000 + 5;
3. int prime[maxn];
4. void getPrime() {
5. memset(prime, 0, sizeof(prime));
6. for (int i = 2; i <= maxn; i++) {
7. if (!prime[i]) prime[++prime[0]] = i;
8. for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {
9. prime[prime[j] * i] = 1;
10. if (i % prime[j] == 0) break;
11. }
12. }
13. }
素数判定
题目描述：
给你两个数a、b,现在的问题是要判断这两个数组成的区间内共有多少个素数
输入描述：
多组测试数据。 每个测试数据输入两个数a、b。(2<=a,b<=1000)
输出描述：
输出该区间内素数的个数。
输入样例#:
2 4
4 6
输出样例#:
2
1
题目来源：
DreamJudge 1102
题目解析：这道题的数据范围不大，我们可以用挨个暴力判断的方法来解决。我们假设这道题的数据范围很大，使用素数筛选的方法来解决这个问题。
参考代码
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. // 线性素数筛选 prime[0]存的是素数的个数
5. const int maxn = 1000000 + 5;
6. int prime[maxn];
7. void getPrime() {
8. memset(prime, 0, sizeof(prime));
9. for (int i = 2; i <= maxn; i++) {
10. if (!prime[i]) prime[++prime[0]] = i;
11. for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {
12. prime[prime[j] * i] = 1;
13. if (i % prime[j] == 0) break;
14. }
15. }
16. }
17. int main() {
18. getPrime();//先进行素数筛选预处理
19. int a, b;
20. while (scanf("%d%d", &a, &b) != EOF) {
21. if (a > b) swap(a, b);//a有可能比b大
22. int ans = 0;
23. for (int i = 1; i <= prime[0]; i++) {
24. if (prime[i] >= a) ans++;//素数大于a答案加一
25. if (prime[i] > b) {
26. ans--;//大于b要减回来
27. break;
28. }
29. }
30. printf("%dn", ans);
31. }
32. return 0;
33. }
练习题目
DreamJudge 1375 素数
