Alexandra and Prime Numbers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1658    Accepted Submission(s): 565

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, or output 0 if no solution exists.

 

 

Sample Input

3 4 5 6

 

 

Sample Output

1 2 1 2

题解：让找最小的正整数M使N/M是素数；

水暴力，但是完全暴力会超，就想着折半找，先找这个最小正整数，如果不行就找素数；都找到sqrt(N)结束，这样就省了好多时间；

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;bool is_prim(int x){    if(x == 1)return false;    for(int i = 2; i <= sqrt(x); i++){        if(x % i == 0)return false;    }    return true;}int main(){    int N;    while(~scanf("%d",&N)){        if(N == 0 || N == 1){            puts("0");continue;        }        int i;        int ans = 0;        for(i = 1; i <= sqrt(N); i++){            if(N % i == 0 && is_prim(N/i)){                ans = i;                break;            }        }        if(ans){            printf("%d\n",ans);continue;        }            for(int j = sqrt(N); j > 1; j--){                if(N % j == 0 && is_prim(j)){                    ans = N / j;                    break;                }        }        printf("%d\n",ans);    }    return 0;}