HDU 5108Alexandra and Prime Numbers（大素數）

HDU 5108Alexandra and Prime Numbers（大素數）

Problem Description Alexandra has a little brother. He is new to programming. One day he is solving the following problem: Given an positive integer N, judge whether N is prime.
The problem above is quite easy, so Alexandra gave him a new task: Given a positive integer N, find the minimal positive integer M, such that N/M is prime. If such M doesn't exist, output 0.
Help him!
Input There are multiple test cases (no more than 1,000). Each case contains only one positive integer N.
N≤1,000,000,000.
Number of cases with N>1,000,000 is no more than 100.
Output For each case, output the requested M, Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciBvdXRwdXQgMCBpZiBubyBzb2x1dGlvbiBleGlzdHMuCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">3 4 5 6
Sample Output

1
2
1
2

對於此題，我只想說自己好傻的，對於一個大數n,求最小的m是的n/m是素數

首先 n=素數*素數*素數......

那麼我們求最大的素數，還有這個素數中不可能有兩個大於sqrt（n）的，那麼代碼如下

#include
#include
#include
#include
#include
#include

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

using namespace std;
typedef __int64 ll;

#define N 100000

ll a[N],b[N];
ll k;

void inset()
{
	int i,j;
	a[0]=1;
	for(i=2;i1;m--)
			if(n%m==0)
		  {
			 while(n%m==0&&!a[m])
				n/=m;

			 if(!a[m])
			 {
			 	ans=max(ans,m);
			 }
		  }
		ans=(ll)max(ans,n);
		printf("%I64d\n",temp/ans);
	}
	return 0;
}