Task — Count primes

You are given a positive integer, $n. Write a script to find the total number of primes less than or equal to the given integer.

Analysis

It seems a bit mean to use a module to deliver the primes, so I have recycled a prime number generator from week 198.

Eratosthenes

So in summary, I generate an array @sieve such that $sieve[$n] is 1 if $n is prime and 0 if it isn't. I generate it using the method discovered by Eratosthenes of Cyrene rather a long time ago.

It's then just a case of counting the 1s from 2 to $n.

I could optimise by reusing @sieve in subsequent calls, but as it stands it copes with $n == 1000000 in just a couple of seconds, so why bother?

Try it 

Script

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-06-26
use utf8;     # Week 223 task 1 - Count primes
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

count_primes(10);
count_primes(1);
count_primes(20);
count_primes(17);
count_primes(1000000);

sub count_primes {
    
    my ($number, @sieve, $j, $count);
    
    $number = shift @_;
    
    # count primes
    if ($number > 1) {
        @sieve = make_sieve($number);
        for $j (2 .. $number) {
            $count += $sieve[$j];
        }
        
    # $number is 0 or 1
    } else {
        $count = 0;
    }
    
    say qq[\nInput:  \$n = $number\nOutput: $count];
}

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:  $n = 10
Output: 4

Input:  $n = 1
Output: 0

Input:  $n = 20
Output: 8

Input:  $n = 17
Output: 7

Input:  $n = 1000000
Output: 78498