Miller-Rabin素数测试算法(快速判素数 )

2023-11-09 15:48

本文主要是介绍Miller-Rabin素数测试算法(快速判素数 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

复杂度  O(k*log3(n))

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[10]={2,3,5,7,11,13,17,19,23,29};
int Quick_Multiply(int a,int b,int c)  //快速积(和快速幂差不多)
{long long ans=0,res=a;while(b){if(b&1)ans=(ans+res)%c;res=(res+res)%c;b>>=1;}return (int)ans;
}
int Quick_Power(int a,int b,int c)     //快速幂,这里就不赘述了
{int ans=1,res=a;while(b){if(b&1)ans=Quick_Multiply(ans,res,c);res=Quick_Multiply(res,res,c);b>>=1;}return ans;
}
bool Miller_Rabin(int x)     //判断素数
{int i,j,k;int s=0,t=x-1;if(x==2)  return true;   //2是素数if(x<2||!(x&1))  return false;     //如果x是偶数或者是0,1,那它不是素数while(!(t&1))  //将x分解成(2^s)*t的样子{s++;t>>=1;}for(i=0;i<10&&prime[i]<x;++i)      //随便选一个素数进行测试{int a=prime[i];int b=Quick_Power(a,t,x);      //先算出a^tfor(j=1;j<=s;++j)    //然后进行s次平方{k=Quick_Multiply(b,b,x);   //求b的平方if(k==1&&b!=1&&b!=x-1)     //用二次探测判断return false;b=k;}if(b!=1)  return false;   //用费马小定律判断}return true;   //如果进行多次测试都是对的,那么x就很有可能是素数
}
int main()
{int x;scanf("%d",&x);if(Miller_Rabin(x))  printf("Yes");else  printf("No");return 0;
}

 

这篇关于Miller-Rabin素数测试算法(快速判素数 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/377072

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb

Python的端到端测试框架SeleniumBase使用解读

《Python的端到端测试框架SeleniumBase使用解读》:本文主要介绍Python的端到端测试框架SeleniumBase使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录SeleniumBase详细介绍及用法指南什么是 SeleniumBase?SeleniumBase

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

python多线程并发测试过程

《python多线程并发测试过程》:本文主要介绍python多线程并发测试过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、并发与并行?二、同步与异步的概念?三、线程与进程的区别?需求1:多线程执行不同任务需求2:多线程执行相同任务总结一、并发与并行?1、

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs