Counting primes and

maximising cash

Weekly challenge 223 — 26 June 2023

Week 223 - 26 Jun 2023

Task 1

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.

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?

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

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

The content of
this website
is licensed by
Peter
Campbell Smith under a
Creative Commons Attribution 4.0 International Licence