ZeroJudge B362: Primes

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".
142 7
630 0
917747257 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

Comments