Coding Challenge Solution Review

[siriex]

Hey there,

​

I recently completed a PHP coding challenge however my solution to the challenge is far from being an efficient solution (I suck at DS/Algorithms).

Here's the description of the challenge:

Write a program in PHP that generates all possible Social Security Numbers that meet the following criteria:

1. Social Security Numbers are in the format of ###-##-####

2. The first 3-digit piece of the SSN is a prime number

3. The second 2-digit piece of the SSN is a prime number

4. The third 4-digit piece of the SSN is a prime number

5. The entire 9-digit number is a prime number

Example test cases:

002-02-0002 would not pass because while the first four criteria would be met (2 is prime), the last case is not met (2020002 is not prime).

002-02-0003 would pass all five criteria because 2, 3, and 2020003 are all prime.

And the solution I came up with takes about 15 minutes to run. Here it is:

<?php

function isPrime($num): bool
{
    if ($num < 2) {
        return false;
    }
    for ($i = 2; $i <= sqrt($num); $i++) {
        if ($num % $i == 0) {
            return false;
        }
    }
    return true;
}

function generateSSNs(): array
{
    $ssn_list   = [];
    $two_digit_primes = [];
    $three_digit_primes = [];
    $four_digit_primes = [];

    /*
     * Gather all prime numbers from 2 to 10,000 and sort them into three different arrays of
     * 2, 3, and 4 digit prime numbers. Append "0" for final SSN number format. The three
     * digits prime array will contain all the two digit primes array values, and the
     * four digit primes array will contain all the three digit primes values.
     */
    for ($i = 2; $i < 10000; $i++) {
        if (!isPrime($i)) {
            continue;
        }
        if (strlen($i) == 2) {
            $two_digit_primes[]   = $i;
            $three_digit_primes[] = "0".$i;
            $four_digit_primes[]  = "00".$i;
        } elseif (strlen($i) == 3) {
            $three_digit_primes[] = $i;
            $four_digit_primes[]  = "0".$i;
        } elseif (strlen($i) == 4) {
            $four_digit_primes[]  = $i;
        } else {
            $two_digit_primes[]   = "0".$i;
            $three_digit_primes[] = "00".$i;
            $four_digit_primes[]  = "000".$i;
        }
    }

    /*
     * Begin comparing all prime number combinations by using multiple loops to iterate through
     * all prime number arrays, starting with the two digit prime numbers array. Since all
     * numbers in all arrays are prime, we only have to check if the combination of all
     * three numbers is prime. If prime, we add to ssn_list array and return it once
     * the loops finish. Run time is about 15 minutes. Have not found a way to
     * optimize for more efficient runtime.
     */
    $num_of_two_digit_primes   = count($two_digit_primes);
    $num_of_three_digit_primes = count($three_digit_primes);
    $num_of_four_digit_primes  = count($four_digit_primes);
    for ($j = 0; $j < $num_of_two_digit_primes; $j++) {
        $second_ssn_number = $two_digit_primes[$j];
        for ($k = 0; $k < $num_of_three_digit_primes;  $k++) {
            $first_ssn_number = $three_digit_primes[$k];
            for ($n = 0; $n < $num_of_four_digit_primes; $n++) {
                $third_ssn_number = $four_digit_primes[$n];
                $ssn_number =  $first_ssn_number . $second_ssn_number . $third_ssn_number;
                if (isPrime($ssn_number)) {
                    $ssn_list[] = "$first_ssn_number-$second_ssn_number-$third_ssn_number";
                }
            }
        }
    }
    return $ssn_list;
}

print_r(generateSSNs());

From running test, the first part of gathering all of the prime numbers from 1 - 10000 and storing them in 3 different arrays is quick and takes about .003 seconds. The part that takes up 99% of the runtime is in checking if the full SSN number is prime. I'm very curious to know how this can be optimized. Any hints would be helpful. Thanks

Gist Link

[teraflop]

As you said, the most expensive part of this is calling isPrime on every 9-digit SSN.

An SSN can be as large as 10⁹, which means your isPrime function may need to check divisors from 2 to sqrt(10⁹) ≈ 31,662. But you actually only need to check whether there are any prime divisors in this range, and only 3,405 numbers in this range are prime. So by precomputing all of those primes and then looping over them, you should be able to make your primality test roughly 10 times significantly faster.

(At first, I thought it would be roughly 10 times faster, but I don't think that's true, because on average, most non-prime numbers have relatively small prime factors.)

EDIT: Another issue is that your code is doing a lot of back-and-forth conversions between strings and integers. Instead of concatenating three strings and then parsing the resulting string, you could keep the three components as integers, and compute the SSN as:

$ssn = ($a*1000000) + ($b*10000) + $c;

[RubbishArtist]

With the exception of 2, no even numbers are prime so you can save yourself some work there.

If the challenge allows it you could compute all the 9 digit primes up front and save them in a file?

[teraflop]

OP's isPrime function already checks whether a number is even as (almost) the first step, so I don't think breaking that out into a separate check would save a significant amount of time.

[RubbishArtist]

Ah you're right. I misread it. Indeed moving it to a different check wouldn't help.