目錄

判斷一個(gè)數(shù)是否為素?cái)?shù)

方法1?

方法2? ?

2.1

2.2

進(jìn)階：輸出區(qū)間長度內(nèi)的素?cái)?shù)

判斷一個(gè)數(shù)是否為素?cái)?shù)

“素?cái)?shù)和質(zhì)數(shù)沒有區(qū)別，素?cái)?shù)又叫質(zhì)數(shù)，質(zhì)數(shù)是指在大于1的自然數(shù)中，除了1和它本身以外，不能被其他自然數(shù)整除的數(shù)。比1大但不是素?cái)?shù)的數(shù)稱為合數(shù)，1和0既非素?cái)?shù)也非合數(shù)?！?/p>

所謂素?cái)?shù)，是指除了1和其本身外，不能被其它任何整數(shù)整除的正整數(shù)，2是最小的素?cái)?shù)。

現(xiàn)在，用戶輸入一個(gè)整數(shù)，判斷它是否為素?cái)?shù)。

方法1?

是指除了1和其本身外，不能被其它任何整數(shù)整除的正整數(shù)

for循環(huán)遍歷2~輸入的數(shù)值num，num對這些數(shù)取余（求模），余數(shù)是0代表能整除，代表不是素?cái)?shù)，如果不是素?cái)?shù)，標(biāo)志位置1，跳出循環(huán)判斷標(biāo)志位的狀態(tài)即可

#include <stdio.h>

int main(void) {
	int i, j;
	int num;
	char flag = 0;	//0代表是素?cái)?shù)，1代表不是
	scanf("%d", &num);	//輸入

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

	if (flag == 1)	//判斷標(biāo)志位即可知是否為素?cái)?shù)
		printf("%d不是素?cái)?shù)\n", num);
	else
		printf("%d是素?cái)?shù)\n", num);
	return 0;
}

方法2? ?

當(dāng)一個(gè)數(shù)不是質(zhì)數(shù)時(shí)，必定存在兩個(gè)約數(shù)，一個(gè)大于等于sqrt(n)，另一個(gè)小于sqrt(n)。利用這種特性，可以對方法1進(jìn)行改進(jìn)，只判斷數(shù)n能否被小于sqrt(n)的數(shù)整除。

小于平方根和大于平方根的部分是一一對應(yīng)的，因而可以只判斷從2到平方根的數(shù)字是否都能被整除即可。

2.1

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

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

	k = sqrt(num);	//先開平方，減小運(yùn)算量
	for (i = 2; i <= k; i++) {
		if (num % i == 0) {
			flag = 1;
			break;	//只要有能整除的數(shù)，就跳出循環(huán)判斷，減小運(yùn)算量
		}
	}

	if (flag == 1)	//判斷標(biāo)志位即可知是否為素?cái)?shù)
		printf("%d不是素?cái)?shù)\n", num);
	else
		printf("%d是素?cái)?shù)\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)    //只要有能整除的數(shù)，就跳出循環(huán)判斷，減小運(yùn)算量
			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;
}

進(jìn)階：輸出區(qū)間長度內(nèi)的素?cái)?shù)

比如打印1000到2000內(nèi)的素?cái)?shù)

#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("%d\n", i);
		}
		i = i + 1;
	}
	printf("\n");
	return 0;
}

?用函數(shù)封裝一下，直接調(diào)用這個(gè)函數(shù)即可輸出素?cái)?shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-440485.html

#include <stdio.h>

void prime(int x, int y) // 區(qū)間（x，y）
{
    int num; // 當(dāng)前判斷的數(shù)
    char flag = 0;
    // 外層循環(huán)，遍歷區(qū)間（x，y）內(nèi)的數(shù)
    for (int j = x; j <= y; j++)
    {
        num = j;

        // 內(nèi)層循環(huán)，判斷當(dāng)前數(shù)，是否為素?cái)?shù)
        for (int i = 2; i < num; i++)
        {
            if (num % i == 0) // 能整除，就不是素?cái)?shù)
            {
                flag = 1;
                break; // 跳出內(nèi)層循環(huán)，遍歷下一個(gè)數(shù)
            }
        }

        if (flag == 0)
            printf("%d\n", num);

        flag = 0; // 在判斷下一個(gè)數(shù)之前，先把標(biāo)志位置0
    }
}

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

到了這里，關(guān)于【C語言】判斷一個(gè)數(shù)是否為素?cái)?shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！