数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序，用于执行贝利-PSW 素数测试
贝利-PSW 素数测试因罗伯特·贝利、卡尔·波梅伦斯、约翰·塞尔弗里奇和塞缪尔·瓦格斯塔夫而得名。此测试用于测试一个数字是合成数还是质数。
算法
MillerTest()
Begin Declare a function MillerTest of Boolean type. Declare MT_dt and MT_num of integer datatype and pass as the parameter. Declare MT_a and MT_x of integer datatype. Initialize MT_a = 2 + rand( ) % (MT_num - 4). Initialize MT_x = pow(MT_a, MT_dt, MT_num). if (MT_x == 1 || MT_x == MT_num - 1) then return true. while (MT_dt != MT_num - 1) do MT_x = (MT_x * MT_x) % MT_num. MT_dt *= 2. if (MT_x == 1) then return false; if (MT_x == MT_num - 1) then return true. return false. End.
示例
#include <iostream>
#include<stdlib.h>
using namespace std;
int pow(int pow_a, unsigned int pow_b, int pow_c) {
int result = 1;
pow_a = pow_a % pow_c;
while (pow_b > 0) {
if (pow_b & 1)
result = (result * pow_a) % pow_c;
pow_b = pow_b >> 1;
pow_a = (pow_a * pow_a) % pow_c;
}
return result;
}
bool MiillerTest(int MT_dt, int MT_num) {
int MT_a = 2 + rand( ) % (MT_num - 4);
int MT_x = pow(MT_a, MT_dt, MT_num);
if (MT_x == 1 || MT_x == MT_num - 1)
return true;
while (MT_dt != MT_num - 1) {
MT_x = (MT_x * MT_x) % MT_num;
MT_dt *= 2;
if (MT_x == 1)
return false;
if (MT_x == MT_num - 1)
return true;
}
return false;
}
bool prime(int P_N, int P_K) {
if (P_N <= 1 || P_N == 4)
return false;
if (P_N <= 3)
return true;
int P_D = P_N - 1;
while (P_D % 2 == 0)
P_D /= 2;
for (int i = 0; i < P_K; i++)
if (MiillerTest(P_D, P_N) == false)
return false;
return true;
}
int main() {
int iter = 50;
long num1;
long num2;
cout<< "Enter the first number: ";
cin>>num1;
cout<<endl;
if (prime(num1, iter))
cout<<num1<<" is a prime number\n"<<endl;
else
cout<<num1<<" is a composite number\n"<<endl;
cout<<"Enter another number: ";
cin>>num2;
cout<<endl;
if (prime(num2, iter))
cout<<num2<<" is a prime number\n"<<endl;
else
cout<<num2<<" is a composite number\n"<<endl;
return 0;
}输出
Enter the first number: 23 23 is a prime number Enter another number: 45 45 is a composite number
更新于：2019 年 7 月 30 日
452 次浏览
广告