C++如何判斷一個數(shù)是不是素數(shù)
更新時間：2022年07月25日 16:35:12 作者：ChanJose
這篇文章主要介紹了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)文章
這篇文章主要為大家詳細(xì)介紹了C++的深淺拷貝和寫時拷貝，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了VC小技巧匯總之控件技巧,對于VC的開發(fā)很有借鑒價值,需要的朋友可以參考下2014-07-07
下面小編就為大家?guī)硪黄胋oost獲取時間并格式化的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
引用是C++一個很重要的特性,顧名思義是某一個變量或?qū)ο蟮膭e名，對引用的操作與對其所綁定的變量或?qū)ο蟮牟僮魍耆葍r,這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識點,需要的朋友可以參考下2022-03-03
這篇文章主要介紹了使用c++實現(xiàn)OpenCV圖像橫向&縱向拼接，文中有圖像拼接函數(shù)，可以實現(xiàn)如“長圖拼接王”這類小程序的類似功能，大家可以將該函數(shù)封裝在軟件中自由使用2021-08-08
C語言數(shù)組學(xué)習(xí)之特殊矩陣的壓縮存儲
矩陣在計算機圖形學(xué)、工程計算中都占有舉足輕重的地位，本文將討論如何將矩陣更有效地存儲在內(nèi)存中，并且能夠方便地提取矩陣中的元素。感興趣的同學(xué)可以了解一下2021-12-12
VS2019開發(fā)Linux C++程序的實現(xiàn)步驟
由于很多unix特有的函數(shù)無法在Windows上使用，而Vim又用的不太順手，突然想到最初用vs的時候有一個基于Linux的C++開發(fā)。本文就來介紹一下，感興趣的可以了解一下2021-07-07
這篇文章主要介紹了C++最優(yōu)二叉樹哈夫曼樹算法解析,哈夫曼樹又稱最優(yōu)二叉樹,是一種帶權(quán)路徑長度最短的二叉樹,所謂樹的帶權(quán)路徑長度,就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度,需要的朋友可以參考下2023-08-08
HttpClient可以實現(xiàn)所有HTTP的方法，通過API傳輸接收HTTP消息。本文詳細(xì)講解了HttpClient，以及如何運用C++實現(xiàn)HTTP客戶端，感興趣的朋友可以參考一下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C++中的類與對象，使用數(shù)據(jù)庫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02