目录

判断一个数是否为素数

方法1 

方法2   

2.1

2.2

进阶：输出区间长度内的素数

判断一个数是否为素数

“素数和质数没有区别，素数又叫质数，质数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。比1大但不是素数的数称为合数，1和0既非素数也非合数。”

所谓素数，是指除了1和其本身外，不能被其它任何整数整除的正整数，2是最小的素数。

现在，用户输入一个整数，判断它是否为素数。

方法1 

是指除了1和其本身外，不能被其它任何整数整除的正整数

for循环遍历2~输入的数值num，num对这些数取余（求模），余数是0代表能整除，代表不是素数，如果不是素数，标志位置1，跳出循环判断标志位的状态即可

#include <stdio.h>

int main(void) {
	int i, j;
	int num;
	char flag = 0;	//0代表是素数，1代表不是
	scanf("%d", &num);	//输入

	for (i = 2; i < num; i++) {
		if (num % i == 0) {	//如果能整除，标志位置1
			flag = 1;
		}
	}

	if (flag == 1)	//判断标志位即可知是否为素数
		printf("%d不是素数n", num);
	else
		printf("%d是素数n", num);
	return 0;
}

方法2   

当一个数不是质数时，必定存在两个约数，一个大于等于sqrt(n)，另一个小于sqrt(n)。利用这种特性，可以对方法1进行改进，只判断数n能否被小于sqrt(n)的数整除。

小于平方根和大于平方根的部分是一一对应的，因而可以只判断从2到平方根的数字是否都能被整除即可。

2.1

#include <stdio.h>
#include <math.h>

int main() {
	int num, k, i;
	char flag = 0;
	scanf("%d", &num);

	k = sqrt(num);	//先开平方，减小运算量
	for (i = 2; i <= k; i++) {
		if (num % i == 0) {
			flag = 1;
			break;	//只要有能整除的数，就跳出循环判断，减小运算量
		}
	}

	if (flag == 1)	//判断标志位即可知是否为素数
		printf("%d不是素数n", num);
	else
		printf("%d是素数n", num);
	return 0;
}

2.2

#include <stdio.h>
#include <math.h>

int main() {
	int m, k, i;
	scanf("%d", &m);

	k = sqrt(m);
	for (i = 2; i <= k; i++) {
		if (m % i == 0)    //只要有能整除的数，就跳出循环判断，减小运算量
			break;
	}
	
	if (m >= 2) {
		if (i > k)
			printf("%d is a prime.", m);
		else
			printf("%d is not a prime.", m);
	} else
		printf("%d is not a prime.", m);
	return 0;
}

进阶：输出区间长度内的素数

比如打印1000到2000内的素数

#include <stdio.h>

int main() {
	int i = 1000;
	while (i <= 2000) {
		int flag = 0;
		int j = 2;

		while (j < i) {
			if (i % j == 0) {
				flag += 1;
			}
			j = j + 1;
		}
		if (flag == 0) {
			printf("%dn", i);
		}
		i = i + 1;
	}
	printf("n");
	return 0;
}

 用函数封装一下，直接调用这个函数即可输出素数

#include <stdio.h>

void prime(int x, int y) // 区间（x，y）
{
    int num; // 当前判断的数
    char flag = 0;
    // 外层循环，遍历区间（x，y）内的数
    for (int j = x; j <= y; j++)
    {
        num = j;

        // 内层循环，判断当前数，是否为素数
        for (int i = 2; i < num; i++)
        {
            if (num % i == 0) // 能整除，就不是素数
            {
                flag = 1;
                break; // 跳出内层循环，遍历下一个数
            }
        }

        if (flag == 0)
            printf("%dn", num);

        flag = 0; // 在判断下一个数之前，先把标志位置0
    }
}

int main()
{
    prime(1000, 2000);
}