输出第M到第N个素数的所有素数
本帖最后由 Ranbo_ 于 2020-3-1 00:02 编辑令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，输出PM到PN的所有素数。
要求：每10个数字占1行，其间以空格分隔，但行末不得有多余空格。
这是pat真题。因为我没学过算法，所以我的思路很简单，就是直接一个一个输入判断，为了防止运行时间超出限制，需要了解一点，即判断一个数n是否为素数，只需要看2~sqrt(n)以内的数是否为n的因数即可。时间复杂度应该是O(n^3/2)。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int is_prime(int n)
{
if(n == 2)
return 1;
for(int i = 2; i <= sqrt(n); i++)
{
if(n % i == 0)
return 0;
}
return 1;
}
int main()
{
int m, n;
scanf("%d %d", &m, &n);
int count = 0;//count记录素数的个数
int sum = 0;//sum记录输出了的素数的个数
int num = 2;//num从2开始一直自增
int i;
while(count != m)
{
if(is_prime(num))
count++;
num++;
}
//此时num-1为第m个素数
if(m == n)
printf("%d\n", num-1);
else
printf("%d ", num-1);
sum = 1;
while(count != n)
{
if(is_prime(num))
{
sum++;count++;
if((sum % 10 == 0) || count == n)
printf("%d\n", num);
else
printf("%d ", num);
}
num++;
}
}
这个题有一种其他做法：埃拉托斯特尼筛法 ------ 要得到自然数n以内的全部素数，必须把不大于sqrt(n)的所有素数的倍数剔除，剩下的就是素数。
实现：用一个长度为N+1的数组保存信息，先将数组所有元素初始化为0，从第一个素数2开始，把2的倍数都标记为非素数（置1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。但是这样需要大概了解第10000个素数的大小。
页:
[1]