随机算法里的大数因子分解(Pollard Rho启发式算法),vc++6.0中实现,写的时候测的数比较小,只用了int,懒得改了,再用的时候再改成更大的数据类型:
001 #include<iostream>
002 #include<vector>
003 #include<algorithm>
004 #include<cmath>
005 #include<stdlib.h>
006
007 using namespace std;
008
009 int randint(int l,int u)
010 {
011 return l+rand()%(u-l+1);
012 }
013
014 int gcd(int m,int n)
015 {
016 return n?gcd(n,m%n):m;
017 }
018
019 bool isPrime(int n)
020 {
021 if(n<2)
022 return true;
023 for(int i=2;i<=pow(n,0.5);i++)
024 if(n%i==0)
025 return false;
026 return true;
027 }
028
029 //判断分解是否结束:0,恰好结束
030 // 1,超过被分解数
031 // 2,分解数不够
032 int ifenough(int n,vector<int>f)
033 {
034 int m=1;
035 for(int i=0;i<f.size();i++)
036 {
037 m*=f[i];
038 }
039 if(m==n)
040 return 0;
041 if(m>n)
042 return 1;
043 return 2;
044 }
045 void PollardRho(int num,int n,vector<int>& f )
046 {
047
048 if(isPrime(n))
049 {
050 f.push_back(n);
051 return;
052 }
053
054 vector<int> x;
055 int i=1;
056 x.push_back(-1);
057 x.push_back(randint(1,n));
058
059 int y=x[1];
060 int k=2;
061 while(true)
062 {
063 i++;
064 x.push_back((abs(x[i-1]*x[i-1]-1))%n);
065
066 int d=gcd(abs(y-x[i]),n);
067
068 if(d>1&&d<n)
069 {
070 PollardRho(num,d,f);
071 PollardRho(num,n/d,f);
072 }
073
074 if(i==k)
075 {
076 y=x[i];
077 k=2*k;
078 }
079
080 if(find(x.begin(),x.end()-1,x[i])!=x.end()-1||ifenough(num,f)==0||ifenough(num,f)==1)
081 {
082 break;
083 }
084 }
085 }
086
087 void repeatRho(int n)
088 {
089 vector<int> f;
090 for(int i=0;i<10000;i++)
091 {
092 f.clear();
093 PollardRho(n,n,f);
094
095 if(ifenough(n,f)==0)
096 {
097 sort(f.begin(),f.end());
098 for(int j=0;j<f.size();j++)
099 {
100 if(j!=f.size()-1)
101 cout<<f[j]<<"*";
102 else
103 cout<<f[j];
104 }
105 cout<<endl;
106 break;
107 }
108 }
109 }
110 int main()
111 {
112 int n;
113 cin>>n;
114 repeatRho(n);
115 }
分享到:
相关推荐
数据结构中的一种重要随机算法--Las Vegas算法,它总是给出正确的结果,但在少数应用中,可能出现求不出解的情况。也是用了50,500,5000子串验证的
skybox对拉斯维加斯某公路的凝视,可以看到路面的汽车穿梭如织,展示多目标检测和跟踪结果
这是本科算法(DS,DATA STRUCTURE)课程中中最重要的三种算法:KMP, Monte Carlo 和Las Vegas算法。资源里有做好的KMP, Monte Carlo 和Las Vegas算法代码以及2份算法报告。
关于概率随机算法,包含数值随机算法,las Vegas算法,Monte Carlo算法,Sherwood算法
N皇后问题Las Vegas优化算法的实现
las-vegas.zip
Vegas_AB:改善Vegas与Reno之间的公平性,徐兵,张旭,尽管TCP Vegas比TCP Reno可以达到更好的吞吐以及更低的重传率,但其在推广过程中仍有不少阻碍。研究表明Vegas在与Reno共享带宽时表现得不�
随机算法实现N皇后问题,所用随机算法是Las Vegas随机算法
稀疏非负卷积的确定性和拉斯维加斯算法_Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution.pdf
这是东南大学计算机系数据结构(data structure)的KMP, Monte Carlo 和Las Vegas算法的程序类实现,里面有代码,报告。
哈工大算法实验四,随机算法求解八皇后问题 Las Vegas算法 1.实现了随机算法与回溯法相结合 2.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
高仿真painter色板PScs4插件painterswheel
Vegas随机转场脚本可以轻松解决做视频或者电子相册时遇到的给每个转场添加脚本的困难。打开Vegas--工具--运行脚本
拉斯维加斯介绍LasVegas.pptx
随机快速排序、随机选择、随机采样这三种算法的实现,并且,采用直接读取后台数据,不需要手工输入
添加到您的Chrome浏览器Las Vegas新标签并获得当地的新闻,当地的天气预报以及最近的景点和旅行亮点Las Vegas提供的景点。 随着我们最喜欢的网站快捷方式,我们的扩展是100%免费 此产品具有大量TLC,100%免费。 ...
利用随机算法判断某个串是否为另一个串的字串 利用随机算法判断某个数是否为素数(较大的素数,20万以上)
是ntp-4.2.4p6@vegas-v2-o-win32的命令解释,主要是方便服务器的各种命令使用。
前端项目-vegas,拉斯维加斯-全屏背景和幻灯片。
2019-拉斯维加斯 DevOps Enterprise Summit 2019幻灯片 10月28日至30日拉斯维加斯大都会