C++怎么判斷一個數(shù)是不是素數(shù)

這篇文章主要介紹“C++怎么判斷一個數(shù)是不是素數(shù)”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“C++怎么判斷一個數(shù)是不是素數(shù)”文章能幫助大家解決問題。

如何判斷一個數(shù)是不是素數(shù)

題目：判斷一個數(shù)是不是素數(shù)，1 < N <= 50000

思路

判斷n是否整除（求余是否等于0）大于1而小于sqrt(n)中的任何一個數(shù)，如果有則不是素數(shù)，否則是素數(shù)

實(shí)現(xiàn)代碼

//  判斷一個數(shù)是不是素數(shù)，1 < N <= 50000 
#include <iostream> 
#include <cmath> 
using namespace std; 
 
// 如果為真，即是素數(shù)；否則，不是素數(shù)
bool isPrime(int n) { 
    int i; 
    for(i = 2; i <= sqrt(n); i++) { 
        if((n % i) == 0) // 如果能被除了1和它本身的數(shù)整除，就不是素數(shù) 
            return false; 
    } 
    return true; // 是素數(shù) 
} 
 
int main(int argc, const char * argv[]) { 
    int n; 
    bool isFlag;    
 
    while(cin >> n) { 
        isFlag = isPrime(n); // 調(diào)用判斷是否是素數(shù)的函數(shù) 
        if(isFlag) 
            cout << n << "是素數(shù)" << endl; 
        else 
            cout << n << "不是素數(shù)" << endl; 
    } 
    return 0; 
}

快速判斷一個數(shù)是不是素數(shù)(質(zhì)數(shù))

樸素的方法

判斷從2到sqrt(n)是否有數(shù)可以與其整除。

下面介紹一個更快的方法

質(zhì)數(shù)有一個分布規(guī)律&mdash;&mdash;大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。栗子：5和7，11和13。

由此進(jìn)行剪枝，達(dá)到優(yōu)化的效果。

Code

#include<iostream>
#include<cmath>
using namespace std;
int prime(int num)   //判斷素數(shù) 
{
	if (num == 1)
		return 0;
	if (num == 2 || num == 3)
		return 1;
	if (num % 6 != 1 && num % 6 != 5)
		return 0;
	int tmp = sqrt(num);
	for (int i = 5; i <= tmp; i += 6)
		if (num % i == 0 || num % (i + 2) == 0)
			return 0;
	return 1;
}
int main()
{
	int n;
	cin >> n;
	if (prime(n)) cout << "這個數(shù)是素數(shù)" << endl;
	else cout << "這個數(shù)不是素數(shù)" << endl;
}

關(guān)于“C++怎么判斷一個數(shù)是不是素數(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。