[已解决]输出素数

Hydrogen.

原题为输出第n个素数

#include<stdio.h>
#include<math.h>
int main()
{
        int n, i, j, k = 1;
        int x, array[500000];//x判断素数标记，array储存素数 
        int a;//储存开根号的值 
        scanf("%d",&n);
        array[0] = 2;
        if(n <= 500000 && n >= 2)
        {
                for(i = 3; i <= 500000 ; i+=2)
            {
                    x = 0;
                    a = sqrt(i);
                    for(j = 2; j <= a; j++)
                        { 
                    if(i % j == 0) 
                                {
                                        x = 1;
                                }                        
                }
                if(x!=1)
                {
                        array[k++] = i;
                        }        
            }
        }
        for(i = 0; i < n; i++)
        {
                printf("%d, %d\n", array[i], i+1);        
        }        
        return 0;
}

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

最佳答案

月排行榜 / 总排行榜

梦回连营

2021-9-12 23:12:07

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int);

int main(void){
        int n, i;
        int p = 0;
        printf("how many prime you want know: ");
        scanf("%d", &n); 
        int array[n];
        array[0] = 2;
        for (i = 3; n > 0; i += 2){
                if (is_prime(i)){
                        n--;
                        array[++p] = i;
                }    
        }
        
        for (int j = 0; j < sizeof(array)/sizeof(array[0]); j++)
                printf("the NO.%d prime is: %d\n", j+1, array[j]);
        return 0;
}

bool is_prime(int num){
        if (num <= 2)
                return true;
        for (int i = 2; i * i <= num; i++)
                if (num % i == 0)
                        return false;

        return true;
}

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

跳转到最佳答案楼层

梦回连营

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int);

int main(void){
        int n, i;
        printf("enter which prime: ");
        scanf("%d", &n);
        for (i = 2; n > 0; i++){
                if (is_prime(i))
                        n--;
        }
        printf("the prime you want know is %d", i-1);
        return 0;
}

bool is_prime(int num){
        if (num <= 2)
                return true;
        for (int i = 2; i * i <= num; i++)
                if (num % i == 0)
                        return false;

        return true;
}

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

梦回连营

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int);

int main(void){
        int n, i;
        int p = 0;
        printf("how many prime you want know: ");
        scanf("%d", &n); 
        int array[n];
        array[0] = 2;
        for (i = 3; n > 0; i += 2){
                if (is_prime(i)){
                        n--;
                        array[++p] = i;
                }    
        }
        
        for (int j = 0; j < sizeof(array)/sizeof(array[0]); j++)
                printf("the NO.%d prime is: %d\n", j+1, array[j]);
        return 0;
}

bool is_prime(int num){
        if (num <= 2)
                return true;
        for (int i = 2; i * i <= num; i++)
                if (num % i == 0)
                        return false;

        return true;
}

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