素因子分解 （快速筛法&&试除法）

素因子分解 （快速筛法&&试除法）

素因子分解的算法有很多，费马因子分解：比试除法更加高效，是计算机中广泛使用的很多更有效的因子分解算法的基础。二次筛法和数域筛法用于数百位的十进制的大数字。而数字越大数域筛法更好。现在暂时仅仅写了最基础的试除法，更好的算法还等着我去学习~~

#include #includeusing namespace std;const int N=5e6; //有些特殊的数字素因子会特别大,这里筛选出来的素数对某些特殊的大数不能处理int pri[N],cnt; //50000内的素数共有5133个bool number[N+1];void getprime(){cnt = 0;for (int i = 2; i <= N; i++)//快速筛选{ if (!number[i]) pri[++cnt] = i; // means primer. for (int j = 1; j <= cnt && pri[j] * i <= N; j++) { number[i*pri[j]] = 1; if (i % pri[j] == 0)break; }}}int main(){ getprime(); //cout<>n){ if(n==1){printf("1=1\n"); continue; } printf("%d=",n); int pow; bool p=0; for(i=1;i<=cnt;i++){ p=0; pow=0; if(n%pri[i]==0){ printf("%d",pri[i]); n/=pri[i]; pow=1; } while(n%pri[i]==0){ p=1; pow++; n/=pri[i]; } if(p)printf("^%d",pow); if(n==1){ printf("\n"); break; } if(pow)printf("*"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。