HDU 1164 Eddy's research I

题目：

Description

Eddy's interest is very extensive, recently he is interested in prime number. Eddy discover the all number owned can be divided into the multiply of prime number, but he can't write program, so Eddy has to ask intelligent you to help him, he asks you to write a program which can do the number to divided into the multiply of prime number factor . 

Input

The input will contain a number 1 < x<= 65535 per line representing the number of elements of the set. 

Output

You have to print a line in the output for each entry with the answer to the previous question. 

Sample Input

11 9412

Sample Output

11 2*2*13*181

题意：把每个数n写成质因子的乘积形式

思路：用素数筛选法，把每个数的最大质因子的处于位数求出，然后同时保留第i位对应的素数。每次就求出最大质因子，保存下来，然后n=n除以最大质因子，以此类推，求出每次的最大质因子，知道n就是最大质因子为止。

从小到大输出每个质因子。

#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <math.h> #include <queue> #include <vector> #include <map> using namespace std; typedef long long LL; typedef unsigned long long UL; #define MS(x,y) memset(x,y,sizeof(x)) #define rpt(i,l,r) for(int i=l;i<=r;i++) #define rpd(i,r,l) for(int i=r;i>=l;i--) LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);} #define N 1000005 int prime[N]; int primes[N]; void init(){ int sum=0; prime[1]=sum; for(int i=2;i<N;i++){ if(!prime[i]){ sum++; primes[sum]=i; prime[i]=sum; for(int j=i+i;j<N;j+=i){ prime[j]=sum; } } } } int main() { init(); int n; while(scanf("%d",&n)!=EOF) { int temp[100]; int pos=0; while(primes[prime[n]]!=n){ temp[pos]=primes[prime[n]]; n=n/temp[pos]; pos++; } temp[pos]=n; for(int i=pos;i>=0;i--){ printf("%d",temp[i]); if(i!=0) printf("*"); else printf("\n"); } } return 0; }