新北市网站建设_网站建设公司_MongoDB_seo优化

2025年浙江工业大学计算机考研复试机试真题

2025年浙江工业大学计算机考研复试上机真题

历年浙江工业大学计算机考研复试上机真题

历年浙江工业大学计算机考研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

非素数个数

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

求a-b之间的非素数个数

特别的，1也算作素数，区间是[a, b]。

输入输出格式

输入描述:

多组测试数据。 输入两个正整数数a,b，其中a<=b<=10^7。

输出描述:

输出答案。

输入输出样例

输入样例#:

1 10 1 100

输出样例#:

5 74

代码一

1. #include<stdio.h>
2. #include <stdbool.h>
3. #define MAX_N 10000000
4. bool isPrime[MAX_N + 1];
5. int prefix[MAX_N + 1];
6. int main(){
7. for(int i=0; i<MAX_N; i++) isPrime[i]=true;
8. // 标准埃氏筛（1 ~ √n 的倍数全部标记为非素数）
9. for (int i = 2; i * i <= MAX_N; i++) {
10. if (isPrime[i]) {
11. for (int j = i * i; j <= MAX_N; j += i) {
12. isPrime[j] = false;
13. }
14. }
15. }
16. int a, b, i=1;
17. prefix[0]=0;
18. while(MAX_N-i+1) {
19. if(!isPrime[i]) prefix[i]=prefix[i-1]+1;
20. else prefix[i]=prefix[i-1];
21. i++;
22. }
23. while (scanf("%d %d", &a, &b) != EOF) {
24. // O(1)时间得到答案
25. int ans = prefix[b] - prefix[a-1];
26. printf("%d\n", ans);
27. }
28. }

代码二

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int MAXN = 10000010;
4. int main() {
5. ios::sync_with_stdio(false);
6. cin.tie(0);
7. // 预处理筛法
8. vector<bool> is_prime(MAXN + 1, true);
9. vector<int> non_prime_count(MAXN + 1, 0);
10. is_prime[0] = false;
11. is_prime[1] = true; // 按照题目要求，1算作素数
12. // 埃氏筛法
13. for (int i = 2; i * i <= MAXN; i++) {
14. if (is_prime[i]) {
15. for (int j = i * i; j <= MAXN; j += i) {
16. is_prime[j] = false;
17. }
18. }
19. }
20. // 构建非素数个数的前缀和
21. for (int i = 1; i <= MAXN; i++) {
22. non_prime_count[i] = non_prime_count[i - 1] + (is_prime[i] ? 0 : 1);
23. }
24. int a, b;
25. while (cin >> a >> b) {
26. int non_primes = non_prime_count[b] - non_prime_count[a - 1];
27. cout << non_primes << endl;
28. }
29. return 0;
30. }

代码三

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 10000010;
4. int primes[N], s[N], cnt = 0;//primes存储所有质数
5. bool st[N] = {false};//一开始都是质数 不是合数
6. void getprime(int n)
7. {
8. for(int i = 2; i <= n; i++)
9. {
10. if(!st[i])
11. {
12. primes[cnt] = i;
13. cnt++;
14. }
15. for(int j = 0; primes[j] * i <= n; j++)
16. {
17. st[primes[j] * i] = true;//是合数
18. if(i % primes[j] == 0) break;
19. }
20. }
21. for(int i = 2; i <= n; i++)
22. {
23. if(st[i])
24. {
25. s[i] = s[i - 1] + 1;
26. }
27. else s[i] = s[i - 1];
28. }
29. }
30. int main()
31. {
32. int a, b;
33. getprime(N);
34. while(cin >> a >> b)
35. {
36. cout << s[b] - s[a - 1] << endl;
37. }
38. return 0;
39. }