Question

How to find A and B where A and B are prime numbers and A * B = 12349 in C++

Answer 1

#include <iostream>
#include <cmath>

// Function to check if a number is prime
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    int limit = sqrt(n);
    for (int i = 5; i <= limit; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    
    return true;
}

// Function to find the two prime factors A and B
void findAB(int N, int &A, int &B) {
    int limit = sqrt(N);  

    for (int i = 2; i <= limit; i++) {
        if (N % i == 0) {
            int j = N / i;
            if (isPrime(i) && isPrime(j)) {
                A = i;
                B = j;
                return;
            }
        }
    }

    A = B = -1; // No prime factors found
}

int main() {
    int N = 12349;
    int A, B;

    findAB(N, A, B);

    if (A != -1)
        std::cout << "A = " << A << ", B = " << B << std::endl;
    else
        std::cout << "Not found." << std::endl;
}



/*
run:

A = 53, B = 233

*/

 

70+ SQL courses for beginners and professionals