PTA B_1013 数素数
本帖最后由 798236606 于 2020-3-4 17:41 编辑传送门：https://pintia.cn/problem-sets/9 ... /994805309963354112
解：
1.暴力枚举 O( n*sqrt(n) )
#include<stdio.h>
#include<math.h>
int prime; //保存找到的素数
int is_prime(int n)
{
int i, lim = (int)sqrt((double)n);
if (n < 2) return 0;
for (i = 2; i <= lim; i++) //注意是<=
if (n % i == 0) return 0;
return 1;
}
void find_prime(int n) //从2开始找n个素数
{
int i, p_num = 0;
for (i = 2; p_num < n; i++)
if (is_prime(i)) prime = i;
}
int main()
{
int i, m, n;
scanf("%d %d", &m, &n);
find_prime(n);
for (i = m - 1; i < n; i++)
{
printf("%d", prime);
if ((i - m + 2) % 10 == 0) putchar('\n');
else if (i < n - 1) putchar(' ');
}
return 0;
}
2.Eratosthenes筛法 O( nloglogn )
#include<stdio.h>
#define MAXN 1000010 //由于不知道第n个素数多大，在此定义一个足够大的数
int prime; //保存找到的素数
int is_not_p = {0}; //0代表是素数， 1代表是合数
void find_prime(int n) //从2开始找n个素数
{
int i, j, p_num = 0;
for (i = 2; p_num < n; i++)
{
if (!is_not_p) prime = i;
for (j = i + i; j < MAXN; j += i) is_not_p = 1; //把i的倍数都标记为合数
}
}
int main()
{
int i, m, n;
scanf("%d %d", &m, &n);
find_prime(n);
for (i = m - 1; i < n; i++)
{
printf("%d", prime);
if ((i - m + 2) % 10 == 0) putchar('\n');
else if (i < n - 1) putchar(' ');
}
return 0;
}
3.Euler筛法 O( n )
#include<stdio.h>
#define MAXN 1000010 //由于不知道第n个素数多大，在此定义一个足够大的数
int prime; //保存找到的素数
int is_not_p = {0}; //0代表是素数， 1代表是合数
void find_prime(int n) //从2开始找n个素数
{
int i, j, p_num = 0;
for (i = 2; p_num < n; i++)
{
if (!is_not_p) prime = i;
for (j = 0; j < p_num && i * prime < MAXN; j++) //对于每一个已找到的素数， 其i倍（即i * prime）必不是素数
{
is_not_p] = 1;
if (i % prime == 0) break; //如果i是已知素数的倍数，则停止筛选，以免重复筛选同一个数。具体解释见文末
}
}
}
int main()
{
int i, m, n;
scanf("%d %d", &m, &n);
find_prime(n);
for (i = m - 1; i < n; i++)
{
printf("%d", prime);
if ((i - m + 2) % 10 == 0) putchar('\n');
else if (i < n - 1) putchar(' ');
}
return 0;
}
参考资料：https://blog.csdn.net/qq_39763472/article/details/82428602
页:
[1]