Question

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

Answer 1

#include <stdio.h>
#include <math.h>

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

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

// Function to find the two prime factors A and B
void findAB(int N, int *A, int *B) {
    int limit = (int)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)
        printf("A = %d, B = %d\n", A, B);
    else
        printf("Not found.\n");

    return 0;
}


/*
run:

A = 53, B = 233

*/

 

70+ SQL courses for beginners and professionals