2
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Everything is described in the question with given constraints a possible solution and sample input and output. what else should i need to provide? \$\endgroup\$ Commented May 13 at 12:50
  • 2
    \$\begingroup\$ The task looks like some contest problem. What is its origin? \$\endgroup\$
    – CiaPan
    Commented May 13 at 15:28
  • 1
    \$\begingroup\$ The question 'is there any other way to solve the problem...' has an obvious answer 'of course there is'. Despite that, it rather poorly fits the CodeReview profile, which is finding out what could be made better in your code with respect to readability, safety, maintainability, portability etc., and not necessarily 'how do I get the solution within a given time limit'. \$\endgroup\$
    – CiaPan
    Commented May 13 at 15:36
  • 1
    \$\begingroup\$ For more info please see our Help center with its Asking section, especially first three topics: How do I ask a good question?, What topics can I ask about here?, and What types of questions should I avoid asking?. \$\endgroup\$
    – CiaPan
    Commented May 13 at 15:42
  • \$\begingroup\$ Hint 1. Suppose your input array contains 20 elements, all equal 1000. Your code will have to analyze one thousand numbers, from 1 to 1000, for each item of the input array. So it will repeat the same work twenty times. Can you think of some way to avoid it? \$\endgroup\$
    – CiaPan
    Commented May 21 at 20:47

1 Answer 1

2
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.