C语言笔记 —— 判断质数（普通，进阶）

判断一个数是不是质数非常的简单，首先我们需要明白判断质数的逻辑，根据质数本身的定义，只能被1和自己本身整除的数，我们称之为质数，而2是最小的质数，因此最简单的逻辑实现，就是循环遍历2到我们想要判断的数之间的所有数，通过判断我们给定的数能否被遍历的数整除，最终决定他是否是质数，实现代码如下：

# include 

void main()
{
	int num = 0;
	scanf("%d", &num);
	printf("%d", num_is(num));
}
int num_is(int num)
{
	for (int i = 2; i < num; i++)
	{
		if (num % i == 0) return 0;
	}
	return 1;
}

此时，当我们输入的数为质数时，打印1，否则打印0，由此我们便完成了判断质数的逻辑，但假如，现在我们想要判断多个数是否为质数，如果我们想要求1000以内的所有质数，那其实也很简单，我们只要写一个2 - 1000的循环遍历 （2是最小的质数），每次调用一下我们写的这个函数就可以了，代码实现如下：

# include 

void main()
{
	int num = 1000;
	for (int i = 2; i <= num; i++)
	{
		if (num_is(i)) printf("%dn", i);
	}
}
int num_is(int num)
{
	for (int i = 2; i < num; i++)
	{
		if (num % i == 0) return 0;
	}
	return 1;
}

此时，我们便打印出了1000以内的所有质数了，但我们发现，此时，我们需要完成完整的两层for循环，是否可以做出一定的简化呢？

当然可以，如果我们已经知道了2是最小的质数，那么我们可以知道所有的2的倍数都不可能是质数，3是质数，那么3的所有的倍数也都不可能是质数了，接着到4，因为4是2的倍数，所以，4不是质数，因此我们可以定义一个数组，其大小由我们给定的要判断的数的数量而定，下标为我们要判断的数，而数组内通过0和1来标记该下标所对应的数是否为质数，实现代码如下：

# include 
# include 
int num_is(int num);
void main()
{
	int num = 1000;
	num_is(num);
}
int num_is(int num)
{
	int* arr = malloc((num+1)*sizeof(int));
	for (int i = 0; i <= num; i++)
		arr[i] = 1;
	for (int i = 2; i <= num; i++)
	{
		if (arr[i] == 1)
		{
			for (int j = i + i; j <= num; j += i)
				arr[j] = 0;
		}
	}
	for (int i = 2; i <= num; i++)
	{
		if (arr[i] == 1)
		{
			printf("%dn", i);
		}
			
	}
	free(arr);
	return 0;
}