C语言实现：判断素数（两种方法，含思路过程）_c语言判断素数

一、题目

  判断一个正整数a是否为素数，若是素数，则函数返回1，不是素数返回0。

二、思路

  众所周知，质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

方法一：计数法

  用for循环来循环出2到 i 的数，在每一次循环的同时进行一次 if 语句判断，判断它是否可以被整除，可以整除的话count ++一次，直到循环结束，再次进行 if 语句判断，判断count是否等于2，上述所知，素数只有1和本身两个因数，等于2 就是素数，返回1，不等于2，不是素数，返回0。
以下是部分代码：

#include<stdio.h>

int isprime(int i)
{
	int count = 0;	//计数
	for (int m = 1; m <= i; m++)	
	{
		if (i % m == 0)		//循环往复，
		{					//每次遇到可以 %m 等于 0 的count都++一次
			count++;
		}
	}
	if (count == 2)	//到这里循环结束，判断count是否等于2
	{
		return 1;	//返回1
	}
	else
	{
		return 0;	//返回0
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：平方根法

  素数只有两个因数，那么用 sqrt 函数来求出 i 的平方根，再进行判断是否能被整除。用 for循环执行2到 i 的平方根，在每一次循环的同时进行一次 if 语句判断，判断它是否可以被整除，可以被整除直接返回0，因为能被2到 i 的平方根之间的值整除，就证明这个数不止两个因数。

#include<stdio.h>
#include<math.h>	//使用sqrt

int isprime(int i)
{
	for (int m = 2; m <= sqrt(i); m++)	//sqrt就是求出输入数的平方根
	{
		if (i % m == 0)		
		{
			return 0;		//进入这个语句就证明i不止两个因数
		}
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、完整代码

方法一代码：

#include<stdio.h>

int isprime(int i)
{
	int count = 0;	//计数
	for (int m = 1; m <= i; m++)	
	{
		if (i % m == 0)		//循环往复，
		{					//每次遇到可以 %m 等于 0 的count都++一次
			count++;
		}
	}
	if (count == 2)	//到这里循环结束，判断count是否等于2
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main()
{
	int i, j;
	printf("请输入大于1的整数:");
	scanf("%d", &i);	//输入
	j = isprime(i);		//调用函数
	if (j == 1)			//判断返回的值是否为1
	{
		printf("%d是素数", i);
	}
	else
	{
		printf("%d不是素数", i);
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

---

方法二代码：

#include<stdio.h>
#include<math.h>	//使用sqrt

int isprime(int i)
{
	int m;
	for ( m = 2; m <= sqrt(i); m++)	//sqrt就是求出输入数的平方根
	{
		if (i % m == 0)		
		{
			return 0;		//进入这个语句就证明i不止两个因数
		}
	}
	return 1;
}

int main()
{
	int i, x;
	printf("请输入大于1的整数:");
	scanf("%d", &i);
	if (i <= 0)
	{
		printf("输入错误！");
	}
	else
	{
		x = isprime(i);
		if (x)		//等价于x != 0
		{
			printf("%d是素数", i);
		}
		else
		{
			printf("%d不是素数", i);

		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40