Alexandra and Prime Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1847 Accepted Submission(s): 629
Problem DescriptionAlexandra
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! InputThere 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. OutputFor each case, output the requested M, or output 0 if no solution exists. Sample Input3
4
5
6 Sample Output1
2
1
2题意:给出一个数 n ,找到最小的 m ,使得 n/m 是质数,如果不存在,输出 0.题解:对于一个整数n(n>=2) n= p1^e1*p2^e2…pk^ek所以要把n 分解成一个质数,那么最大的质数必定是他最大的质因子,所以分解 n,得到最大的质因子,n/MAXPRIME 即为 m的最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include <queue>
using namespace std;
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int id = ,MAX=;
int m = n;
for(int i=;i*i<=n;i++){
if(n%i==){
MAX = max(i,MAX);
while(n%i==) n/=i;
}
}
MAX = max(n,MAX);
if(MAX==) printf("0\n");
else printf("%d\n",m/MAX);
}
return ;
}