数据结构
网络
关系数据库管理系统
操作系统
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+ 次查看
广告