Cデータ構造の分解素因数

1.分解素因数
正の整数Nの素因数の個数を求めて、同じ素因数は繰り返し計算する必要があります.例えば120=2*2*2*3*5.データ群毎にNの素因数個数を出力する.
サンプル入力:120サンプル出力5(1はNの素因数ではなく、Nが素数であればNはNの素因数)
構想:素数ふるい法を用いて,所与のデータ範囲内で素因数になる可能性のあるすべての素数を予めスクリーニングする.n未満のすべての素数を順次遍歴し,nの因数であるか否かを判断する.場合、対応するべき乗指数は、試除によって決定されます.最後に,各べき乗指数の和を求めた.
1.nを入力
2.ステップ1で得られた素数がnを除去できるかどうかを順次試験し、できればその素数が彼の素数であることを示す.
3.nを素数で除算し続け、これ以上除算できなくなるまで.同時にべき乗指数を統計します.
4.ある素数のべき乗指数統計が完了すると、nが1となると、nのすべての素因数がすべて分解され、分解が停止することを示す.
5.すべての前処理された素数を遍歴、テスト、分解した後もnが1に除かれていない場合、nは100000より大きい因子が存在することを示し、その因子は必ずその素数であり、べき乗指数は1である.

#include
bool mark[100001];
int prime[100001];
int primeSize;
void init()//    
{
	primeSize=0;
	for(int i=2;i<=100000;i++)
	{
		if(mark[i]==true) continue;
		prime[primeSize++]=i;
		if(i>=1000) continue;
		for(int j=i*i;j<=100000;j+=i)
		{
			mark[j]=true;
		}
	}
} 
int main()
{
	init();
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int ansPrime[30];//             
		int  ansSize=0;//          
		int ansNum[30];//              （   ） 
		for(int i=0;i

2.問題の整理
nを与えて、aは最大のkを求めて、nを使います!a^kでは除去できるがa^(k+1)では除去できない
考え方:整数aが整数bを除去できる場合:aに素因数Pxが存在する場合、bにも必ずその素因数が存在する.素因数bに対応するべき乗指数は、aにおけるべき乗指数よりも小さくなければならない.最大の非負の整数kを決定するには、aのいずれかの素因数のべき乗指数のk倍がxの素因数に対応するべき乗指数よりも小さいか、または等しいようにする.kを要求するには、aの各素数を順次テストし、bの素因数に対応するべき乗指数がaの何倍であるかを決定するだけで(整除法を用いて)、すべての倍数の中で最も小さいものが私たちが要求するkである.では、n!に対して素因数をどのように分解するか.ステップは以下の通りである.
1.計算機は0をクリアし、このカウンタはnを表す!いくつかのp因子、すなわちn!質量係数を分解した後の素因子pに対応するべき乗指数.
2.n/pを計算し、n/p個の整数がnに向かうことができる!p因子が1つ提供されると、カウンタはn/pを累積する.n/pが0の場合,p因子は与えられず,分解は終了する.
3.n/(p*p)を計算し、n/(p*p)個の整数がn!に2個のp因子を提供することができるが、彼らの前のステップのpの倍数は必ずp*pの倍数を含み、各数はすでにアキュムレータに1つのp因子を累積したので、ここではn/(p*p)個の素因子を提供する.0とする.分解が終わる.
4.pのより高い倍数を順次加算して提供できる素因数の個数、すなわち、n/(p^k)が0になるまでカウンタに加算され、整数がより多くのp因子を提供できないことを示し、分解が終了する.カウンタ加算の結果は素因数pのべき乗指数である.

#include 
#include
bool mark[1010];
int prime[1010];
int primeSize;
void init()
{
	primeSize=0;
	for(int i=2;i<10000;i++)
	{
		if(mark[i]) continue;
	//	mark[i]=true;
		prime[primeSize++]=i;
		for(int j=i*i;j<1000;j+=i)
		mark[j]=true;
	}
}//   0 1000         
int cnt[1010];//cnt[i]    ，prime[i]       n！     ， prime[i]     
int cnt2[1010];//cnt2[i]    ，prime[i]       a     
int main()
{
	int n,a;
	init();
	while(scanf("%d%d",&n,&a)==2)
	{

		for(int i=0;i