Alexandra and Prime Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 706 Accepted Submission(s): 247
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.
Number of cases with
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
Source BestCoder Round #19
Recommend heyang | We have carefully selected several similar problems for you: 5111 5110 5109 5107 5106
题意 ： 给你一个N 寻找一个最小M ，使得N/M=素数 不解释了，简单代码 #include
#include
#include
#include
using namespace std;
int f(int x)
{
int flag = 0;
for(int i = 2; (i*i) <= x; i ++)
{
if(x % i == 0)
{
break;
}
}
if(flag) return 0;
return 1;
}
int main()
{
int n;
int mark[200005];
while(scanf("%d",&n)!=EOF)
{
if( n == 1 ) {printf("0\n"); continue;}
int count = 0, flag = 0;
for(int i = 1; (i * i) <= n; i++)
{
if( n%i == 0) {mark[count++] = i; mark[count++] = n / i;}
}
sort(mark, mark + count);
int i;
for(i = count - 1 ; i >= 0; i --)
{
if(f(mark[i])) { break;}
}
printf("%d\n",n / mark[i]);
}
}