-
-
[原创]质因数分解C版
-
2009-7-3 19:22
6976
-
【原创】质因数分解C版
最大数支持4294967294也就是scanf("%lu")最大的数。
因为分解4294967294只需要
65535的质数表。所以速度很快。
理论上2.5×10^17的分解都可以在很短的时间内分出来。
2.5×10^17需要500000000的质数表。这里的算法我机器用了12.015 s
质数表部分算法参考了arab和erex的算法。并做了一些优化.
http://bbs.pediy.com/showthread.php?t=89497
但是只用到30因为30就可以节省3/4的空间用到2310 也就节省4/5.对速度影响较重。
arab的算法算500000000需要71s
没做空间优化的算法因为会用到虚拟内存速度影响很大。
/**
* N*30+1, N*30+7, N*30+11, N*30+13, N*30+17, N*30+19, N*30+23, N*30+29
**/
#include "stdio.h"
#include "math.h"
long unsigned NUM;
char* real;;
long unsigned k;
inline void wtable(register unsigned long a)
{
register unsigned long b;
b=a/30;
a=a%30;
switch(a)
{
case 1:real[b]=real[b]&&!1;break;
case 7:real[b]=real[b]&&!(1<<1);break;
case 11:real[b]=real[b]&&!(1<<2);break;
case 13:real[b]=real[b]&&!(1<<3);break;
case 17:real[b]=real[b]&&!(1<<4);break;
case 19:real[b]=real[b]&&!(1<<5);break;
case 23:real[b]=real[b]&&!(1<<6);break;
case 29:real[b]=real[b]&&!(1<<7);
default:;
}
}
inline int rtable(register unsigned long a)
{
register unsigned long b;
if(a>5)
{
b=a/30;
if(real[b]==0)return 0;
a=a%30;
switch(a)
{
case 1:return real[b]&&1;
case 7:return real[b]&&(1<<1);
case 11:return real[b]&&(1<<2);
case 13:return real[b]&&(1<<3);
case 17:return real[b]&&(1<<4);
case 19:return real[b]&&(1<<5);
case 23:return real[b]&&(1<<6);
case 29:return real[b]&&(1<<7);
default:return 0;
}
}
else
{
switch(a)
{
case 2:return 1;
case 3:return 1;
case 5:return 1;
default:return 0;
}
}
}
void suShu()
{
register unsigned long i=3,j,step;
for(j=0; j<[COLOR="Red"]NUM/30+1[/COLOR]; j++)
{
real[j] = 0xFF;//初始化数组
}
while(i<=k)
{
if(rtable(i)==0)
{
step=i<<1;
for(j=i*i;j<=NUM;j+=step)
wtable(j);
}
++i;
++i;
}
}
int main()
{
unsigned long in;
register unsigned long i;
int f=0;
printf("please inpout the No.:\n");
scanf("%lu",&in);
NUM=(unsigned long)sqrt((long double)in);
real = new char[[COLOR="red"]NUM/30+1[/COLOR]];
k = (long)sqrt((double)NUM);
suShu();
printf("%lu=",in);
for (i=2;i<=NUM;i++)
{
if(rtable(i)==0)
continue;
else
{
if(in%i!=0)
continue;
else
{
in=in/i;
i--;
printf("%ld*",i+1);
f=1;
}
}
}
if(in==1&f==1)printf("\b");
else if(f==1)printf("%ld",in);
else if(in<2)printf("\b can not factorization !");
else printf("\b is prime number !");
return 0;
}
ps：2.5×10^17基本上是56-58位2进制。而真正的RSA一般要求512位密匙。所以RSA还是相当安全的.
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
