Question

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

Answer 1

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

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

    return true;
}

// Helper class to return A and B together
class Pair {
    public $A, $B;
    function __construct($A, $B) {
        $this->A = $A;
        $this->B = $B;
    }
}

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

    for ($i = 2; $i <= $limit; $i++) {
        if ($N % $i == 0) {
            $j = $N / $i;
            if (isPrime($i) && isPrime($j)) {
                return new Pair($i, $j);
            }
        }
    }

    return new Pair(-1, -1); // No prime factors found
}

$N = 12349;

$result = findAB($N);

if ($result->A != -1)
    echo "A = " . $result->A . ", B = " . $result->B . PHP_EOL;
else
    echo "Not found." . PHP_EOL;



/*
run:

A = 53, B = 233

*/

 

70+ SQL courses for beginners and professionals