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!
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.
For each case, output the requested M, or output 0 if no solution exists.
1
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 = 0,MAX=1;
int m = n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
MAX = max(i,MAX);
while(n%i==0) n/=i;
}
}
MAX = max(n,MAX);
if(MAX==1) printf("0\n");
else printf("%d\n",m/MAX);
}
return 0;
}
