C++如何判斷一個數(shù)是不是素數(shù)
如何判斷一個數(shù)是不是素數(shù)
題目:判斷一個數(shù)是不是素數(shù),1 < N <= 50000
思路
判斷n是否整除(求余是否等于0)大于1而小于sqrt(n)中的任何一個數(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ī)律——大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。栗子:5和7,11和13。
由此進行剪枝,達到優(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; }
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
C語言中socket相關(guān)網(wǎng)絡(luò)編程函數(shù)小結(jié)
這篇文章主要介紹了C語言中socket相關(guān)網(wǎng)絡(luò)編程函數(shù)小結(jié),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09C++ 類中有虛函數(shù)(虛函數(shù)表)時 內(nèi)存分布詳解
下面小編就為大家?guī)硪黄狢++ 類中有虛函數(shù)(虛函數(shù)表)時 內(nèi)存分布詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2016-12-12