素数的定义

如果一个正整数p只有两个因子1和p，那么我们称这个数是素数。大于1的非素数是合数，1既不是素数也不是合数

几种判定素数的方法

一、暴力
直接一次检查这个数是不是只有两个因子，这种方法的时间复杂度比较高，为根号下n，也把这种方法叫做素性测试

int is_prime(LL n)
{
    if(n <= 1) return 0;
    LL m = floor(sqrt(n) + 0.5);
    for(LL i = 2; i <= m; i++)
        if(n % i == 0) return 0;
    return 1;
}

二、埃氏筛法
这个方法利用了一个性质：每一个素数的倍数都不是素数。所以我们先初始化所有的数都是0，当一个素数p出现时，我们把n内的p的倍数都标记成1，等到程序结束后那些值为0的数就是素数

int vis[maxn];     //用于在埃氏筛法中判断是否访问过
int prime[maxp];    //用于存储素数

//筛选素数
void sieve(int n)
{
    int m = (int)sqrt(n + 0.5);
    memset(vis,0,sizeof(vis));
    for(int i = 2; i <= m; i++)
        for(int j = i * i; j <= n; j += i)
            vis[j] = 1;
}

真题

PAT1013
https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112

#include <stdio.h>
#include <string.h>

#define N 1100000

int a[N], vis[N];

void init() {
    int cnt = 1;
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= 11000; ++i) {
        if (!vis[i]) {
            for (int j = i + i; j <= 1000000; j += i) {
                vis[j] = 1;
            }
        }
    }
    for (int j = 2; j <= 1000000; ++j) if (!vis[j]) a[cnt++] = j;
}

int main() {
    int n, m;
    init();
    while (scanf("%d %d", &m, &n) != EOF) {
        int cnt = 1;
        for (int i = m; i <= n; ++i) {
            printf("%d%c", a[i], (cnt == 10 || i == n) ? '\n' : ' ');
            cnt = (cnt == 10 ? 1 : cnt + 1);
        }
    }
    return 0;
}