資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中的素數測試
在這個問題中，我們給定一個數字 N，我們的任務是檢查它是否是素數。
素數測試是一種用於檢查給定數字是否為素數的演算法。
素數是一個只能被自身整除的數。例如：2、3、5、7。
讓我們舉個例子來理解我們的問題，
Input: 11 Output: Yes
有多種方法可以檢查數字的素數測試。
一種簡單的檢查素數的方法是檢查該數字是否能被所有小於 N 的數字整除。如果任何數字能整除 N，則它不是素數。
檢查所有 i = 2 - n-1。如果 n/i == 0，則它不是素數。
可以透過對演算法進行以下小的更改來提高此方法的效率。
首先，我們應該檢查直到 √n 的值，而不是 n。這將節省大量的迴圈值。√n 包括 n 的所有可能因子的值。
另一個更改可能是檢查 2 和 3 的除法。然後檢查從 5 到 √n 的迴圈值。
程式演示此演算法的實現
示例
#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main() {
int n = 341;
if (isPrimeNumber(n))
cout<<n<<" is prime Number.";
else
cout<<n<<" is not prime Number.";
return 0;
}輸出
341 is not prime Number.
另一種更有效的方法來檢查數字的素數性是使用費馬方法，該方法基於費馬小定理。
費馬小定理對於素數 N，每個屬於 (1, n-1) 的 x 值。以下為真，
a n-1 ≡ 1 (mod n) or a n-1 % n = 1
程式演示此定理的實現，
示例
#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
int res = 1;
a = a % p;
while (n > 0){
if (n & 1)
res = (res*a) % p;
n = n/2;
a = (a*a) % p;
}
return res;
}
int gcd(int a, int b) {
if(a < b)
return gcd(b, a);
else if(a%b == 0)
return b;
else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
while (k>0){
int a = 2 + rand()%(n-4);
if (gcd(n, a) != 1)
return false;
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
int main() {
int k = 3, n = 23;
if(isPrime(n, k)){
cout<<n<<" is a prime number";
}
else
cout<<n<<" is not a prime number";
return 0;
}輸出
23 is a prime number
更新於: 2020年2月3日
1K+ 次檢視
廣告