Mind the gap!

Weekly challenge 198 — 2 January 2023

Week 198 - 2 Jan 2023

Task 2

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

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

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.

#!/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; }

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain