HDU 5108Alexandra and Prime Numbers（大素数） - c++编程基础

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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciBvdXRwdXQgMCBpZiBubyBzb2x1dGlvbiBleGlzdHMuCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">3 4 5 6
Sample Output

对于此题，我只想说自己好傻的，对于一个大数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;i
        
         1;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; }