C++如何判斷一個(gè)數(shù)是不是素?cái)?shù)
更新時(shí)間：2022年07月25日 16:35:12 作者：ChanJose
這篇文章主要介紹了C++如何判斷一個(gè)數(shù)是不是素?cái)?shù)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
如何判斷一個(gè)數(shù)是不是素?cái)?shù)
題目：判斷一個(gè)數(shù)是不是素?cái)?shù)，1 < N <= 50000
思路
判斷n是否整除（求余是否等于0）大于1而小于sqrt(n)中的任何一個(gè)數(shù)，如果有則不是素?cái)?shù)，否則是素?cái)?shù)
實(shí)現(xiàn)代碼
// 判斷一個(gè)數(shù)是不是素?cái)?shù)，1 < N <= 50000
#include <iostream>
#include <cmath>
using namespace std;
// 如果為真，即是素?cái)?shù)；否則，不是素?cái)?shù)
bool isPrime(int n) {
int i;
for(i = 2; i <= sqrt(n); i++) {
if((n % i) == 0) // 如果能被除了1和它本身的數(shù)整除，就不是素?cái)?shù)
return false;
}
return true; // 是素?cái)?shù)
}
int main(int argc, const char * argv[]) {
int n;
bool isFlag;
while(cin >> n) {
isFlag = isPrime(n); // 調(diào)用判斷是否是素?cái)?shù)的函數(shù)
if(isFlag)
cout << n << "是素?cái)?shù)" << endl;
else
cout << n << "不是素?cái)?shù)" << endl;
}
return 0;
}快速判斷一個(gè)數(shù)是不是素?cái)?shù)(質(zhì)數(shù))
樸素的方法
判斷從2到sqrt(n)是否有數(shù)可以與其整除。
下面介紹一個(gè)更快的方法
質(zhì)數(shù)有一個(gè)分布規(guī)律——大于等于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) //判斷素?cái)?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 << "這個(gè)數(shù)是素?cái)?shù)" << endl;
else cout << "這個(gè)數(shù)不是素?cái)?shù)" << endl;
}以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++的深淺拷貝和寫時(shí)拷貝，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了VC小技巧匯總之控件技巧,對(duì)于VC的開發(fā)很有借鑒價(jià)值,需要的朋友可以參考下2014-07-07
下面小編就為大家?guī)硪黄胋oost獲取時(shí)間并格式化的方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-03-03
C++中引用的相關(guān)知識(shí)點(diǎn)小結(jié)
引用是C++一個(gè)很重要的特性,顧名思義是某一個(gè)變量或?qū)ο蟮膭e名，對(duì)引用的操作與對(duì)其所綁定的變量或?qū)ο蟮牟僮魍耆葍r(jià),這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識(shí)點(diǎn),需要的朋友可以參考下2022-03-03
使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV圖像橫向&縱向拼接，文中有圖像拼接函數(shù)，可以實(shí)現(xiàn)如“長(zhǎng)圖拼接王”這類小程序的類似功能，大家可以將該函數(shù)封裝在軟件中自由使用2021-08-08
C語言數(shù)組學(xué)習(xí)之特殊矩陣的壓縮存儲(chǔ)
矩陣在計(jì)算機(jī)圖形學(xué)、工程計(jì)算中都占有舉足輕重的地位，本文將討論如何將矩陣更有效地存儲(chǔ)在內(nèi)存中，并且能夠方便地提取矩陣中的元素。感興趣的同學(xué)可以了解一下2021-12-12
VS2019開發(fā)Linux C++程序的實(shí)現(xiàn)步驟
由于很多unix特有的函數(shù)無法在Windows上使用，而Vim又用的不太順手，突然想到最初用vs的時(shí)候有一個(gè)基于Linux的C++開發(fā)。本文就來介紹一下，感興趣的可以了解一下2021-07-07
這篇文章主要介紹了C++最優(yōu)二叉樹哈夫曼樹算法解析,哈夫曼樹又稱最優(yōu)二叉樹,是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹,所謂樹的帶權(quán)路徑長(zhǎng)度,就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度,需要的朋友可以參考下2023-08-08
HttpClient可以實(shí)現(xiàn)所有HTTP的方法，通過API傳輸接收HTTP消息。本文詳細(xì)講解了HttpClient，以及如何運(yùn)用C++實(shí)現(xiàn)HTTP客戶端，感興趣的朋友可以參考一下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C++中的類與對(duì)象，使用數(shù)據(jù)庫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02