2011年上海交通大学计算机研究生机试真题

整除问题

http://ac.jobdu.com/problem.php?id=1104

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#include<memory.h>

int prime[170],num;
void findPrime(int n) 
{ 
	int i,j,k,flag;
	prime[0]=2;
	num=1;
	for(i=3;i<=n;i+=2)   //奇数才有可能是素数，偶数就可以直接忽略了
	{
		k=sqrt(i*1.0);
		flag=0;
		for(j=3;j<=k;j+=2)    //奇数肯定无法整除偶数，所以只需要判断是否能否整除奇数就可以了，只要有一个能够整除，就不是素数
		{
			if(i%j==0)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
			prime[num++]=i;
	}
}

int main(void)
{
	int i,n,a,p,m,hash[1000],h,max;
	findPrime(1000);
	
	while(scanf("%d %d",&n,&a)!=EOF)
	{
		max=1000;
		memset(hash,0,sizeof(hash));
		for(i=0;prime[i]<=a && i<num;i++)
		{
			p=prime[i];
			m=0;
			while(a%p==0)
			{
				m++;
				a/=p;
			}
			hash[p]=m;
			if(a==1)
				break;
		}
		h=n;
		p=2;
		for(m=0;h/=p;)      //n!中2的个数可表示为 n/2+n/4+... 
				m+=h;
		if(hash[2])
		{
			if(m/hash[2]<max)
				max=m/hash[2];
		}
		for(i=3;i<1000;i+=2)
		{
			if(hash[i])
			{
				p=i;
				h=n;
				for(m=0;h/=p;)      //道理同上
					m+=h;
				if(m/hash[i]<max)
					max=m/hash[i];
			}
		}
		printf("%d\n",max);
	}
	return 0;
}