C语言中判断素数的几种方法

作为C的初学者们希望大家看看这几种判断素数的方法

既然进来了就看完把

题目要求：

判断n是否为素数。

首先我们讲一下素数的判定：素数就是只能被1或者本身整除的数，这就延伸出了几种不同的判定方法。

方法一：因为判断素数相当于就是判断这个数能不能整除2-这个数之间的所有数，如果有就不是素数。否则就是素数。

#include<stdio.h>
int main()
{
	int i, n;
	scanf("%d", &n);
	if (n <= 2)
	{
		printf("%d不是素数\n", n);
	}
	else
	{
		for (i = 2; i <= n - 1; i++)
		{
			if (n % i == 0)
				break;
		}
		if (i >= n)
			printf("%d是素数\n", n);
		else
			printf("%d不是素数\n", n);
	}

	return 0;
}

​

运行结果如下

方法二 ：由方法一很容易想到可以把范围再缩小一点缩小到2-n/2

#include<stdio.h>
int main()
{
	int i, n;
	scanf("%d", &n);
	for (i = 2; i <= n/2; i++)
	{
		if (n % i == 0)
			break;
	}
	if (i == n/2+1)
		printf("%d是素数\n", n);
	else
		printf("%d不是素数\n", n);
	return 0;
}

运行结果如下

方法三：那我们也可以得出取2-√n之间的数来进行。

#include<stdio.h>
#include<math.h>//sqrt()需要引用的头文件
int main()
{
	int i, n;
	scanf("%d", &n);
	for (i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)
			break;
	}
	if (i >sqrt(n))
		printf("%d是素数\n", n);
	else
		printf("%d不是素数\n", n);
	return 0;
}

 运行结果如下：