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 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