Task — Prime count

You are given an integer $n > 0. Write a script to print the count of primes less than $n

Examples

Example 1
Input: $n = 10
Output: 4 as there are 4 primes less than 10 
which are 2, 3, 5, 7

Example 2
Input: $n = 15
Output: 6

Example 3
Input: $n = 1
Output: 0

Example 4
Input: $n = 25
Output: 9

Analysis

We are asked to find the number of primes less than a supplied number.

Many previous weeks' tasks have involved primes, so I had an implementation of the Sieve of Eratosthenes to hand. It's then just a case of counting them:

@sieve = make_sieve($test - 1);
$output = 0;
for $j (2 .. $test - 1) {   # ignore 1 and $test
    $output ++ if $sieve[$j];
}

Even with $test equal to a million, this only takes a couple of seconds to run.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2023-02-03
# PWC 198 task 2

use v5.28;
use utf8;
use warnings;


my (@tests, $test, @sieve, $output, $j);
@tests = (10, 15, 1, 25, 17, 2, 1000, 1000000);

# loop over tests
for $test (@tests) {
    
    # make sieve of Eratosthenes
    @sieve = make_sieve($test - 1);
    
    # count primes
    $output = 0;
    for $j (2 .. $test - 1) {
        $output ++ if $sieve[$j];
    }
    say qq[\nInput:  $test\nOutput: $output];
}

sub make_sieve {
    
    # make sieve of Eratosthenes : $sieve[$j] = is_prime($j) ? 1 : 0;
    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = $_[0];
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }
    
    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime     
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
    return @sieve;
}

Output

Input:  10
Output: 4

Input:  15
Output: 6

Input:  1
Output: 0

Input:  25
Output: 9

Input:  17
Output: 6

Input:  2
Output: 0

Input:  1000
Output: 168

Input:  1000000
Output: 78498