- 注册时间
- 2009-5-22
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 38591
- 在线时间
- 小时
|
发表于 2010-1-27 00:22:55
|
显示全部楼层
本来想新发一个主题贴的。
但发之前搜索了一下，发现有好多相关内容。
而且我要发的代码与这个贴子的主题再贴切不过了。
所以就直接贴在这里了。
#####
我把楼主的想法实现了一下，发现做出来的效果并不是太好。
大家看看我用的方法与传说中RHO是不是完全一样的，是不是一字不差地实现出来了。
我个人觉得分解极端数据的速度好像比试除快不了多少。
所以请大家帮我看看哪里写得不够好，应该如何优化。
如果谁有更好的代码，也贴出来让大家学习学习吧。- #include<cstdio>
- #include<cstdlib>
-
- unsigned long long x;
- unsigned long long m(unsigned long long a,unsigned long long b,unsigned long long n){ //返回a*b%n的结果
- unsigned long long r;
- r=0;
- a%=n;
- b%=n;
- while(b){
- if(b&1){
- if(r+a<r)r=r-n+a;
- else r+=a;
- if(r>=n)r-=n;}
- if((a<<1)<a)a=a-n+a;
- else a<<=1;
- if(a>=n)a-=n;
- b>>=1;}
- return r;}
- unsigned long long v(unsigned long long a,unsigned long long n,unsigned long long b){ //返回a^n%b的结果
- unsigned long long r,p;
- for(r=1,p=a;n;n>>=1){
- if(n&1)r=m(r,p,b);
- p=m(p,p,b);}
- return r;}
- unsigned long long w(unsigned int a,unsigned long long n){ //以a为基测试n
- unsigned long long u,x,q;
- int t;
- u=n-1;
- for(t=0;!(u&1);u>>=1)t++;
- x=v(a,u,n);
- for(;t--;){
- q=m(x,x,n);
- if(q==1&&x-1&&x-n+1)return 1; //返回1表示测试不通过
- x=q;}
- return x-1;} //当且仅当x=1时，测试通过
- unsigned long long z(unsigned long long n){ //判断n是否为素数
- int p[9]={2,3,5,7,11,13,17,19,23},i;
- for(i=0;i<9;++i){
- if(n==p[i])return 1; //n是列表中的素数，返回"是"
- if(w(p[i],n))return 0;} //n没有通过素数基p[i]的测试，返回"否"
- return 1;} //n通过了9个素数基的测试，返回"是"
- unsigned long long h(unsigned long long n){ //分解n
- unsigned long long x,i,d,b,t,y;
- if(!(n&1))return 2;
- for(;;){
- x=rand()+2;y=x;
- for(i=2;;i++){
- x=m(x,x,n);
- if(x)x--;
- else x=n-1;
- d=y>x?y-x:x-y;
- b=n;
- for(;b;){t=d;d=b;b=t%b;} //辗转相除求b和d的最大公约数
- if(d>1&&d<n)return d; //若d不是1也不是n本身，则分解成功
- if(d==n)break;
- if(!(i&(i-1)))y=x;}}}
- void g(unsigned long long x){ //输出x的分解式
- unsigned long long o;
- if(z(x))printf("%I64u",x);
- else{
- o=h(x);
- g(o);
- printf("*");
- g(x/o);}}
- int main(){
- while(scanf("%I64u",&x)>0&&x>1)
- if(z(x))printf("%I64u is a prime.\n",x);
- else{
- printf("%I64u=",x);
- g(x);
- puts("");}
- return 0;}
A.rar
(7.32 KB, 下载次数: 12)
|
评分
-
查看全部评分
|
IP卡
狗仔卡
发表于 2008-5-15 08:12:13
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
试除
或者RHO算法、ECM
得不到内嵌的代码
不好说
发表于 2008-5-15 09:37:08
