PHP Exercises: Print the number of prime numbers which are less than or equal to a given integer
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:
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:
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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics