C语言代码思路和注释整数之间的素数 描述：求指定的两个整数m、n之间的素数（m<=n) 输入：只有一行，是空格隔开的两个正整数m和n。(m<=n) 输出：在m和n之间（含m和n）的所有素数，按照每个数据占6列，每行5个数据输出。两种方案

方案一：暴力枚举法

思路：对于每个在m和n之间的数，都进行一次素数判断，如果是素数就输出。

C语言代码：

#include <stdio.h>

int is_prime(int x)  // 判断素数函数
{
    int i;
    if(x == 2)  // 特判2
        return 1;
    if(x < 2 || x % 2 == 0)  // 排除偶数和小于2的数
        return 0;
    for(i = 3; i * i <= x; i += 2)  // 枚举奇数
        if(x % i == 0)
            return 0;
    return 1;
}

int main()
{
    int m, n, cnt = 0;
    scanf("%d%d", &m, &n);
    for(int i = m; i <= n; i++)
    {
        if(is_prime(i))
        {
            printf("%6d", i);  // 输出
            cnt++;
            if(cnt % 5 == 0)  // 每行5个数据
                printf("\n");
        }
    }
    if(cnt % 5 != 0)  // 处理最后一行不足5个数据的情况
        printf("\n");
    return 0;
}

注释：

1. `is_prime`函数：判断一个数是否为素数，返回值为1表示是素数，返回值为0表示不是素数。
2. 特判2：2是最小的素数，需要特判。
3. 排除偶数和小于2的数：因为偶数都可以被2整除，所以只需枚举奇数；小于2的数都不是素数。
4. 枚举奇数：从3开始枚举奇数，因为偶数已经被排除了，所以可以直接从3开始，每次加2。
5. 输出：用`printf("%6d", i)`输出一个整数，占6列，右对齐；用`cnt`计数，每输出一个素数，`cnt`加1；每输出5个数据，就换行。
6. 处理最后一行不足5个数据的情况：如果最后一行不足5个数据，就在最后再换行一次。

方案二：埃氏筛法

思路：先用一个数组`is_prime`存储所有可能的素数，然后从小到大枚举每个素数，将它的倍数标记为非素数。

C语言代码：

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

#define MAXN 1000000

int is_prime[MAXN + 1];  // is_prime[i]为1表示i是素数，为0表示i是非素数

int main()
{
    int m, n, cnt = 0;
    scanf("%d%d", &m, &n);
    memset(is_prime, 1, sizeof(is_prime));  // 初始化为全部是素数
    is_prime[0] = is_prime[1] = 0;  // 0和1不是素数
    for(int i = 2; i <= n; i++)
    {
        if(is_prime[i])  // i是素数
        {
            if(i >= m)  // i在[m, n]之间
            {
                printf("%6d", i);  // 输出
                cnt++;
                if(cnt % 5 == 0)  // 每行5个数据
                    printf("\n");
            }
            for(int j = 2 * i; j <= n; j += i)  // 将i的倍数标记为非素数
                is_prime[j] = 0;
        }
    }
    if(cnt % 5 != 0)  // 处理最后一行不足5个数据的情况
        printf("\n");
    return 0;
}

注释：

1. `is_prime`数组：用来存储所有可能的素数，初始时全部赋值为1，表示都是素数。
2. 初始化：0和1都不是素数，所以要将它们标记为非素数。
3. 输出：与方案一相同，但是只输出在[m, n]之间的素数。
4. 埃氏筛法：从小到大枚举每个素数，将它的倍数标记为非素数。如果一个数i是素数，那么它的倍数2i、3i、4i...都不是素数，因为它们都可以分解成i×2、i×3、i×4...。注意：这里从2i开始，因为i的倍数1i已经是i本身，所以不需要标记。

两种方案的时间复杂度都是O((n-m+1)loglogn)，但是方案二的常数要小一些，因为它不需要对每个数都进行素数判断。