C语言基础：回顾判断素数

什么是素数（也称质数）？和合数相对。
其特点是只能被 1 和它本身整除，无法被其他整数整除。或者公因数只有它自己和1两个数的数
在这里插入图片描述

怎么求解素数呢？对于求解质数的方法很多，但是有一种专门求解素数的功能：埃拉托色尼筛选法-这个程序简直就是为求解素数而生。
埃拉托色尼筛选法：埃拉托色尼筛选法（Sieve of Eratosthenes）是一个用来找出一定范围内所有素数的经典算法。这个算法是由古希腊数学家埃拉托色尼发明的。对于C语言实现的描述是：如果自然数i为素数，则设a[i]为1，否则设为0。首先把数组中所有的元素设为1，以表明这些数全部是素数。然后把数组中所有对应的索引处已证明是非素数（一直是素数的倍数）的元素设为0。如果所有的更小的素数的倍数都已经设为0,a[i]仍然为1，则可知它是素数。

我们先从一定范围内N(N=1000)的素数开始，先写一个埃拉托色尼，然后将它打印出来：

#include<stdio.h>
#define N 1000

int main(){
	int i,j,a[N];
	for(i = 2; i < N; i++) a[i] = 1;
	for(i = 2; i < N; i++)
		if(a[i])
			for(j = i; j*i < N; j++) a[j*i] = 0;
	for(i = 2; i < N; i++)
		if(a[i]) printf("%4d",i);
	printf("\n");
}

在这里插入图片描述
注意到这个式子没有问题后，我们着手去实现题目3条：

现在通过 scanf() 函数接收一个正整数 n，判断它是否是质数：
若 n 是质数，通过输出语句输出 [n] is a prime number.
否则，输出 [n] is not a prime number.

前一条非常容易实现：

int num;
scanf("%d",&num);

后两条是两个选择，而且我们通过埃拉托色尼已经将数组中数标记为2类数字了，第一类是值为1的质数，第二类是值为0的合数。
这里我们有两种选择：

第一：使用if else;

	i = num;
	if(a[i]){
		printf("%d is a prime number.",i);
	}else{
		printf("%d is not a prime number.",i);
	}

第二：选择switch（我用的是这个）

    i = num;
    switch(a[i]){
    	case 1:printf("%d is a prime number.",i);break;
    	case 0:printf("%d is not a prime number.",i);break;
    }

注意:我在这里犯了一个错误，那就是误以为是我们输入的数字和数组里面存储的元素比，但不是，这个里我们是和数组元素的索引比较。

完整代码如下：

#include <stdio.h>
#include <stdio.h>
#define N 1000

int main() {
    // 初始化变量
    // Write your code here
    int i,j,a[N],num;

    // 读取用户输入的数
    scanf("%d",&num);

    // 初始化数组，将所有位置都设为1
    for(i = 2; i < N; i++) a[i] = 1;

    // 遍历数组，标记非质数位置为0
    for(i = 2; i < N; i++)
        if (a[i]) 
            for(j = i; i*j < N; j++) a[i*j] = 0;

    // 判断输入数是否为质数，并输出结果
    i = num;
    switch(a[i]){
    	case 1:printf("%d is a prime number.",i);break;
    	case 0:printf("%d is not a prime number.",i);break;
    }    
}

我们测试一下：分别输入4、5（最大能测试999，因为数组下标是从0开始的,数组长度为1000，a[2]~a[999]）
在这里插入图片描述

但是这个依然不符合题目要求：2<=num<=10^5，只要将N修改到100000就超时了。
数据类型的范围点击跳转

理论上随着要求数据的增大只要修改N的值兼顾i,j,a[i]的数据类型就可以了,但是那将需要太多的内存（例如，int a[100000]; 会占用近 4MB 的内存，这在大多数现代系统上是可以接受的，但不是一个好的做法，尤其是如果你打算同时处理多个这样的数组时）。我们需要一个通用的方法，我们需要更加智能的办法。

接下来我们将在埃拉托色尼上加点料，让它更加智能——数组的动态存储分配：通过stdlib.c的库函数malloc，在执行时利用该值为数组动态分配空间。

#include <stdlib.h>
int main(int argc,char *argv[]) {
    long int i,j,N = atol(argv[1]);
    int *a = malloc(N*sizeof(int));
    if (a == NULL)
    	{ printf("Insufficient memory.\n"); return;	}

加入之后的代码如下：

#include <stdio.h>
#include <stdlib.h>


int main(int argc,char *argv[]) {
    // 从命令行参数中获取N的值，并将其转换为长整型
    // Write your code here
    long int i,j,N = atol(argv[1]),num;
    // 动态分配一个大小为N的整型数组a
    int *a = malloc(N*sizeof(int));
    // 如果分配失败，则输出错误信息并退出程序
    if (a == NULL)
    	{ printf("Insufficient memory.\n"); return;	}

    // 从标准输入读取一个整数到变量num
    scanf("%d",&num);
    // 将数组a的第2到第N-1个元素都初始化为1
    for(i = 2; i < N; i++) a[i] = 1;
    // 遍历数组a的第2到第N-1个元素
    for(i = 2; i < N; i++)
        // 如果当前元素为1
        if (a[i]) 
            // 则将数组a中从i开始，以i为公倍数的元素都置为0
            for(j = i; i*j < N; j++) a[i*j] = 0;

    // 将变量num的值赋给i
    i = num;
    // 根据数组a中i位置的值判断num是否为质数，并输出相应的结果
    switch(a[i]){
    	case 1:printf("%d is a prime number.",i);break;
    	case 0:printf("%d is not a prime number.",i);break;
    } 
    // 程序结束，返回0
	return 0;   
}

测试之后结果超时了
在这里插入图片描述
哈哈哈，炫酷了一把，结果还是没有解决，但这种思考让我收获匪浅，留一个悬念，有时间了再研究研究，今天就到这里。
下面有个写得不错的，代码如下：

#include <stdio.h>

/**
 * @brief 判断一个整数是否为质数
 *
 * 读取用户输入的整数，判断该整数是否为质数，并输出相应的结果。
 *
 * @return 程序执行状态码，0 表示执行成功，其他值表示执行失败
 */
int main() {
    // 定义一个整数变量num
    // Write your code here
    int num;
    // 定义一个整数变量isPrime，用于表示是否为质数，初始值为1（是质数）
    int isPrime = 1;
    // 从标准输入读取一个整数赋值给变量num
    scanf("%d",&num);
    // 如果num等于1
    if(num==1){
        // 输出1是质数
        printf("%d is a prime number.\n",num);
    }
    // 从2开始循环到num-1
    for(int i=2;i<num;i++){
        // 如果num能够被i整除
        if(num%i==0){
            // 输出num不是质数
            printf("%d is not a prime number.\n",num);
            // 将isPrime设置为0，表示num不是质数
            isPrime = 0;
            // 跳出循环
            break;
        }
    }
    // 如果isPrime仍然为1，即num是质数
    if(isPrime){
        // 输出num是质数
        printf("%d is a prime number.\n",num);
    }
}