唯一质因子分解方程
每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。
标称：
#include <iostream> #include <cstring> #include <cstdlib> using namespace std; const int MAXN = 65540; int a[MAXN]; int main(){ int n; while(cin >> n && n){ int cnt = 0; for(int i=2;i<=n;++i){ while(n % i == 0){ a[cnt++] = i; n /= i; } } for(int i=0;i<cnt-1;++i){ cout << a[i] << "*"; } cout << a[cnt-1] << endl; } return 0; }
one 试除法：无论素数判定还是因子分解，试除法(Trial Division)都是首先要进行的步骤。令m=n,从2~根n一一枚举，如果当前数能够整除m，那么当前数就是n的素数因子，并用整数m
将当前数除尽为止。
若循环结束后m是大于1的整数，那么此时m也是n的素数因子
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #define N 65535 using namespace std; int factor[N],top; void divide(int n) { for(int i=2; i<=sqrt(n+0.0); i++) { while(n%i==0) { top++; factor[top]=i; n/=i; } } if(n!=1) { top++; factor[top]=n; } for(int i=1; i<=top-1; i++) { printf("%d*",factor[i]); } printf("%d\n",factor[top]); return ; } int main() { int n; while(scanf("%d",&n)!=EOF) { top=0; divide(n); } return 0; }
two：在试除法基础上加上筛法（埃氏筛），减少时间
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #define N 65540 using namespace std; int factor[N],top,cnt,prime[N]; bool b[N]; void make_prime() { top=0; b[0]=b[1]=false; b[2]=true; prime[++top]=2; for(int i=3; i<N; i++) if(i%2==0) b[i]=false; else b[i]=true; double t=sqrt(1000000*1.0); for(int i=3; i<=t; i++) { if(b[i]) { prime[++top]=i; for(int j=i*i; j<N; j=j+i) { b[j]=false; } } } } void divide(int n) { cnt=0; int temp=sqrt(n+0.0); for(int i=1; i<=top; i++) { if(prime[i]>temp) break; while(n%prime[i]==0) { cnt++; factor[cnt]=prime[i]; n/=prime[i]; } } if(n!=1) { cnt++; factor[cnt]=n; } for(int i=1; i<=cnt-1; i++) { printf("%d*",factor[i]); } printf("%d\n",factor[cnt]); return ; } int main() { int n; make_prime(); while(scanf("%d",&n)!=EOF) { divide(n); } return 0; }
