输出素数
原题为输出第n个素数#include<stdio.h>
#include<math.h>
int main()
{
int n, i, j, k = 1;
int x, array;//x判断素数标记，array储存素数
int a;//储存开根号的值
scanf("%d",&n);
array = 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 = i;
}
}
}
for(i = 0; i < n; i++)
{
printf("%d, %d\n", array, i+1);
}
return 0;
}
上面是我的代码，for循环是我用来看哪里输入错了，图中是我n输入500000，然后它for循环输出的数在i循环到比较大时，所输出的值就错了，想问一下是哪里出了问题，
然后还想问一下，算法还能再节省一点时间吗？ 本帖最后由 梦回连营 于 2021-9-12 23:01 编辑
#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;
array = 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); j++)
printf("the NO.%d prime is: %d\n", j+1, array);
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;
}
这段代码实现了你想要的功能。
页:
[1]