Count how many numbers in a range have exactly three divisors

Question

The challenge

Given array a of n numbers, I need to count how many positive numbers less than each aᵢ have exactly 3 divisors.

Constraints

1 <= aᵢ <= 2.5 * 10¹³

In other words,

• the minimum value is 1, and
• the maximum value is 25,000,000,000,000.

Example

Input

[100, 15, 30, 10]

Output

[4, 2, 3, 2] 

Explanation

• range 1-100 has 4 numbers each having three divisors (4, 9, 25, 49).
• range 1-15 has 2 such numbers (4, 9).
• range 1-30 has 2 such numbers (4, 9, 25).
• range 1-10 has 2 such numbers (4, 9).

Notice that all the matching numbers are squares of prime numbers:

• 4 = 2²
• 9 = 3²
• 25 = 5²
• 49 = 7²

The code

function square_of_primes($limit) {
    $result = array();
    for ($i = 2; $i * $i < $limit; $i++) {
        $is_prime = true;
        for ($j = 2; $j * $j <= $i; $j++) {
            if ($i % $j === 0) {
                $is_prime = false;
                break;
            }
        }
        if ($is_prime) {
            $result[] = $i * $i;
        }
    }
    return count($result);
}

function findDivisors($arr) {
    $result = [];
    foreach ($arr as $num) {
        $result[] = square_of_primes($num);
    }
    return $result;
}
    
$arr = [100,10, 30];
$divisors = findDivisors($arr);
echo "<pre>";
print_r( $divisors );

Concerns

Whilst this code gives correct answers for small arrays containing small values, it scales very badly.

We have a time limit of 9 seconds to solve this question. But when the array contains the maximum value of 25,000,000,000,000 then it exceeds that time limit.

Answer 1

PHP isn't my language, so I'll keep to a high-level review of the algorithm.

The function names are misleading. findDivisors() doesn't find divisors, for example.

We're re-calculating the primes for every number in the input array. A better approach would be to create an array of the primes just once, at the beginning of the program, and then re-use it for all the inputs.

Instead of using (slow) trial division to find primes, consider using one of the standard sieves to generate the primes we need.

Outline of the more efficient method:

• Generate primes up to √max(aᵢ) using a prime sieve.
• Transform a by squaring each element, to get a list of squares of primes up to max(aᵢ).
• For each aᵢ, binary search the squared primes to find how many are less than aᵢ. That's your output value.