PTA B_1013 数素数

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805309963354112

解：
1.暴力枚举 O( n*sqrt(n) )

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. int prime[10010];        //保存找到的素数
   
5. 
   
6. int is_prime(int n)
   
7. {
   
8.     int i, lim = (int)sqrt((double)n);
   
9.    
   
10.     if (n < 2) return 0;
    
11.    
    
12.     for (i = 2; i <= lim; i++)        //注意是<=
    
13.         if (n % i == 0) return 0;
    
14.                     
    
15.     return 1;
    
16. }
    
17. 
    
18. void find_prime(int n)        //从2开始找n个素数
    
19. {
    
20.     int i, p_num = 0;
    
21.    
    
22.     for (i = 2; p_num < n; i++)
    
23.         if (is_prime(i)) prime[p_num++] = i;
    
24. }
    
25. 
    
26. int main()
    
27. {
    
28.     int i, m, n;
    
29.    
    
30.     scanf("%d %d", &m, &n);
    
31.    
    
32.     find_prime(n);
    
33.    
    
34.     for (i = m - 1; i < n; i++)
    
35.     {
    
36.         printf("%d", prime[i]);
    
37.                
    
38.         if ((i - m + 2) % 10 == 0) putchar('\n');
    
39.         else if (i < n - 1) putchar(' ');
    
40.     }
    
41. 
    
42.     return 0;
    
43. }

复制代码

2.Eratosthenes筛法 O( nloglogn )

1. #include<stdio.h>
   
2. 
   
3. #define MAXN 1000010        //由于不知道第n个素数多大，在此定义一个足够大的数
   
4. 
   
5. int prime[10010];        //保存找到的素数
   
6. int is_not_p[MAXN] = {0};        //0代表是素数， 1代表是合数
   
7. 
   
8. void find_prime(int n)        //从2开始找n个素数
   
9. {
   
10.     int i, j, p_num = 0;
    
11.    
    
12.     for (i = 2; p_num < n; i++)
    
13.     {
    
14.         if (!is_not_p[i]) prime[p_num++] = i;
    
15.         for (j = i + i; j < MAXN; j += i) is_not_p[j] = 1;      //把i的倍数都标记为合数
    
16.     }
    
17. }
    
18. 
    
19. int main()
    
20. {
    
21.     int i, m, n;
    
22.    
    
23.     scanf("%d %d", &m, &n);
    
24.    
    
25.     find_prime(n);
    
26.    
    
27.     for (i = m - 1; i < n; i++)
    
28.     {
    
29.         printf("%d", prime[i]);
    
30.                
    
31.         if ((i - m + 2) % 10 == 0) putchar('\n');
    
32.         else if (i < n - 1) putchar(' ');
    
33.     }
    
34. 
    
35.     return 0;
    
36. }

复制代码

3.Euler筛法 O( n )

1. #include<stdio.h>
   
2. 
   
3. #define MAXN 1000010        //由于不知道第n个素数多大，在此定义一个足够大的数
   
4. 
   
5. int prime[10010];        //保存找到的素数
   
6. int is_not_p[MAXN] = {0};        //0代表是素数， 1代表是合数
   
7. 
   
8. void find_prime(int n)        //从2开始找n个素数
   
9. {
   
10.     int i, j, p_num = 0;
    
11.         
    
12.     for (i = 2; p_num < n; i++)
    
13.     {
    
14.         if (!is_not_p[i]) prime[p_num++] = i;
    
15.                     
    
16.         for (j = 0; j < p_num && i * prime[j] < MAXN; j++)        //对于每一个已找到的素数， 其i倍（即i * prime[j]）必不是素数
    
17.         {
    
18.             is_not_p[i * prime[j]] = 1;
    
19.             if (i % prime[j] == 0) break;       //如果i是已知素数的倍数，则停止筛选，以免重复筛选同一个数。具体解释见文末   
    
20.         }
    
21.     }
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.     int i, m, n;
    
27.    
    
28.     scanf("%d %d", &m, &n);
    
29.    
    
30.     find_prime(n);
    
31.    
    
32.     for (i = m - 1; i < n; i++)
    
33.     {
    
34.         printf("%d", prime[i]);
    
35.                     
    
36.         if ((i - m + 2) % 10 == 0) putchar('\n');
    
37.         else if (i < n - 1) putchar(' ');
    
38.     }
    
39. 
    
40.     return 0;
    
41. }

复制代码

参考资料：https://blog.csdn.net/qq_39763472/article/details/82428602