[已解决]输出素数

Hydrogen.

原题为输出第n个素数

1. #include<stdio.h>
   
2. #include<math.h>
   
3. int main()
   
4. {
   
5.         int n, i, j, k = 1;
   
6.         int x, array[500000];//x判断素数标记，array储存素数
   
7.         int a;//储存开根号的值
   
8.         scanf("%d",&n);
   
9.         array[0] = 2;
   
10.         if(n <= 500000 && n >= 2)
    
11.         {
    
12.                 for(i = 3; i <= 500000 ; i+=2)
    
13.             {
    
14.                     x = 0;
    
15.                     a = sqrt(i);
    
16.                     for(j = 2; j <= a; j++)
    
17.                         {
    
18.                     if(i % j == 0)
    
19.                                 {
    
20.                                         x = 1;
    
21.                                 }                       
    
22.                 }
    
23.                 if(x!=1)
    
24.                 {
    
25.                         array[k++] = i;
    
26.                         }        
    
27.             }
    
28.         }
    
29.         for(i = 0; i < n; i++)
    
30.         {
    
31.                 printf("%d, %d\n", array[i], i+1);       
    
32.         }       
    
33.         return 0;
    
34. }

复制代码

上面是我的代码，for循环是我用来看哪里输入错了，图中是我n输入500000，然后它for循环输出的数在i循环到比较大时，所输出的值就错了，想问一下是哪里出了问题，
然后还想问一下，算法还能再节省一点时间吗？

最佳答案

月排行榜 / 总排行榜

梦回连营

2021-9-12 23:12:07

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. bool is_prime(int);
   
5. 
   
6. int main(void){
   
7.         int n, i;
   
8.         int p = 0;
   
9.         printf("how many prime you want know: ");
   
10.         scanf("%d", &n);
    
11.         int array[n];
    
12.         array[0] = 2;
    
13.         for (i = 3; n > 0; i += 2){
    
14.                 if (is_prime(i)){
    
15.                         n--;
    
16.                         array[++p] = i;
    
17.                 }   
    
18.         }
    
19.         
    
20.         for (int j = 0; j < sizeof(array)/sizeof(array[0]); j++)
    
21.                 printf("the NO.%d prime is: %d\n", j+1, array[j]);
    
22.         return 0;
    
23. }
    
24. 
    
25. bool is_prime(int num){
    
26.         if (num <= 2)
    
27.                 return true;
    
28.         for (int i = 2; i * i <= num; i++)
    
29.                 if (num % i == 0)
    
30.                         return false;
    
31. 
    
32.         return true;
    
33. }

复制代码

这段代码实现了你想要的功能。

跳转到最佳答案楼层

梦回连营

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. bool is_prime(int);
   
5. 
   
6. int main(void){
   
7.         int n, i;
   
8.         printf("enter which prime: ");
   
9.         scanf("%d", &n);
   
10.         for (i = 2; n > 0; i++){
    
11.                 if (is_prime(i))
    
12.                         n--;
    
13.         }
    
14.         printf("the prime you want know is %d", i-1);
    
15.         return 0;
    
16. }
    
17. 
    
18. bool is_prime(int num){
    
19.         if (num <= 2)
    
20.                 return true;
    
21.         for (int i = 2; i * i <= num; i++)
    
22.                 if (num % i == 0)
    
23.                         return false;
    
24. 
    
25.         return true;
    
26. }

复制代码

这样子能实现寻找到第n个质数，你的第一个for循环里嵌套的if语句没有即时退出，一旦存在i%j==0的时候就说明不是质数了，就可以立即退出循环了，只有遍历完for循环发现没有可以整除的数才可以确定为是质数。还有你的程序里面的50000表示的是小于这个数的质数，并不是第50000个质数。

梦回连营

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. bool is_prime(int);
   
5. 
   
6. int main(void){
   
7.         int n, i;
   
8.         int p = 0;
   
9.         printf("how many prime you want know: ");
   
10.         scanf("%d", &n);
    
11.         int array[n];
    
12.         array[0] = 2;
    
13.         for (i = 3; n > 0; i += 2){
    
14.                 if (is_prime(i)){
    
15.                         n--;
    
16.                         array[++p] = i;
    
17.                 }   
    
18.         }
    
19.         
    
20.         for (int j = 0; j < sizeof(array)/sizeof(array[0]); j++)
    
21.                 printf("the NO.%d prime is: %d\n", j+1, array[j]);
    
22.         return 0;
    
23. }
    
24. 
    
25. bool is_prime(int num){
    
26.         if (num <= 2)
    
27.                 return true;
    
28.         for (int i = 2; i * i <= num; i++)
    
29.                 if (num % i == 0)
    
30.                         return false;
    
31. 
    
32.         return true;
    
33. }

复制代码

这段代码实现了你想要的功能。