Ah-Xuan is a junior high school teacher who has recently taught the unit on prime factorization. To help students practice, he will present a number N and ask the students to answer whether this number is a product of two prime numbers. If it is, they should also state which two prime numbers multiply to give this number.
Please write a program to generate the correct answer.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The input consists of only one line containing a number N9). | If N is the product of two prime numbers A and B (where A ≤ B), output the two prime numbers A and B separated by a single space. If N is not the product of two prime numbers, output "0 0". |
14 | 2 7 |
63 | 0 0 |
917747 | 257 3571 |
Thought Process
To determine the factors of N, you only need to iterate from 2 to sqrt(N) + 1 using a for loop. If there is a factor, check if it's a prime number by verifying if there are any factors between 2 and sqrt(factor) + 1. Also, check if N divided by the factor is a prime number. If it is, you can output the two numbers and break the loop.
Sample Code-ZeroJudge B362: Primes
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int N)
{
for (int i = 2; i<int(sqrt(N))+1; i++)
{
if (N % i == 0) return false;
}
return true;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
bool ok = false;
for (int i = 2; i<int(sqrt(N))+1; i++)
{
if (N % i == 0 && isPrime(i) && isPrime(N / i))
{
ok = true;
cout << i << " " << N/i << "\n";
break;
}
}
if (!ok) cout << "0 0\n";
}
//ZeroJudge N362
//Dr. SeanXD