PTA B_1013 数素数

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805309963354112

解：
1.暴力枚举 O( n*sqrt(n) )

#include<stdio.h>
#include<math.h>

int prime[10010];        //保存找到的素数

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[p_num++] = 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[i]);
                
        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[10010];        //保存找到的素数
int is_not_p[MAXN] = {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[i]) prime[p_num++] = i;
        for (j = i + i; j < MAXN; j += i) is_not_p[j] = 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[i]);
                
        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[10010];        //保存找到的素数
int is_not_p[MAXN] = {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[i]) prime[p_num++] = i;
                    
        for (j = 0; j < p_num && i * prime[j] < MAXN; j++)        //对于每一个已找到的素数， 其i倍（即i * prime[j]）必不是素数
        {
            is_not_p[i * prime[j]] = 1;
            if (i % prime[j] == 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[i]);
                    
        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