PHP Exercises: Print the number of prime numbers which are less than or equal to a given integer

Last update on April 19 2025 11:50:34 (UTC/GMT +8 hours)

52. Count Primes Up to n

Write a PHP program to print the number of prime numbers which are less than or equal to a given integer.

Input:
n (1 ≤ n ≤ 999,999) .

Pictorial Presentation:

PHP: Print the number of prime numbers which are less than or equal to a given integer.

Sample Solution:

PHP Code:

<?php
// Initialize an array to mark numbers as prime or not (Sieve of Eratosthenes)
$a = array_fill(0, 1000000, true);
$a[0] = $a[1] = false;

// Iterate through numbers and mark multiples as non-prime
for ($i = 2; $i * $i < 1000000; $i++) {
    if (!$a[$i]) continue;
    for ($j = $i * $i; $j < 1000000; $j += $i) {
        $a[$j] = false;
    }
}

// Initialize an array to store the cumulative count of prime numbers
$sum = array_fill(0, 1000000, 0);

// Calculate the cumulative count of prime numbers up to each index
for ($i = 1; $i < 1000000; $i++) {
    $sum[$i] += $sum[$i - 1];
    if ($a[$i]) $sum[$i]++;
}

// Read input from standard input until the end of file
while (fscanf(STDIN, "%d", $n)) {
    // Print the number of prime numbers which are less than or equal to n
    echo "Number of prime numbers which are less than or equal to n: ";
    echo $sum[$n] . "\n";
}
?>

Explanation:

Initialization:

An array $a is created with array_fill(0, 1000000, true) to mark numbers as prime (true) or not (false).
The first two indices ($a[0] and $a[1]) are set to false since 0 and 1 are not prime numbers.

Sieve of Eratosthenes Algorithm:

A loop iterates through numbers starting from 2 to the square root of 1,000,000:

for ($i = 2; $i * $i < 1000000; $i++).

Inside this loop, if a number is marked as prime (if (!$a[$i]) continue;), another loop marks its multiples as non-prime:

for ($j = $i * $i; $j < 1000000; $j += $i) { $a[$j] = false; }.

Cumulative Prime Count Initialization:

An array $sum is initialized to hold the cumulative count of prime numbers with array_fill(0, 1000000, 0).

Calculating Cumulative Counts:

A loop runs from 1 to 999,999 to compute how many prime numbers exist up to each index:

The cumulative count is updated by adding the previous count ($sum[$i] += $sum[$i - 1];).
If the current number is prime, the count is incremented (if ($a[$i]) $sum[$i]++;).

Input Reading:

The program continuously reads integer input from standard input (STDIN) until EOF:

while (fscanf(STDIN, "%d", $n)).

Output:

For each input number n, the program prints the number of prime numbers that are less than or equal to n:

echo "Number of prime numbers which are less than or equal to n: "; echo $sum[$n] . "\n";.

Output:

Sample Input: 50
Number of prime numbers which are less than or equal to n: 15

Flowchart:

For more Practice: Solve these Related Problems:

Write a PHP script to count prime numbers up to a given integer using the Sieve of Eratosthenes.
Write a PHP function to efficiently calculate the total number of primes less than or equal to n.
Write a PHP script to implement prime counting with iterative methods and validate the output.
Write a PHP script to filter an array of numbers, counting only those that are prime up to n.

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to compute the amount of the debt in n months.
Next: Write a PHP program to compute the radius and the central coordinate (x, y) of a circle which is constructed by three given points on the plane surface.