The weekly challenge 223 - Task 1: Count Primes

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-223/#TASK1
 3 #
 4 # Task 1: Count Primes
 5 # ====================
 6 #
 7 # You are given a positive integer, $n.
 8 #
 9 # Write a script to find the total count of primes less than or equal to the given integer.
10 #
11 ## Example 1
12 ##
13 ## Input: $n = 10
14 ## Output: 4
15 ##
16 ## Since there are 4 primes (2,3,5,7) less than or equal to 10.
17 #
18 ## Example 2
19 ##
20 ## Input: $n = 1
21 ## Output: 0
22 #
23 ## Example 3
24 ##
25 ## Input: $n = 20
26 ## Output: 8
27 ##
28 ## Since there are 4 primes (2,3,5,7,11,13,17,19) less than or equal to 20.
29 #
30 ############################################################
31 ##
32 ## discussion
33 ##
34 ############################################################
35 #
36 # Counting from 1 upward, we check each number whether it is a prime
37 # If it is, we increment a counter
38 # In order to not recalculate the same thing over and over again, we keep
39 # a cache for numbers already checked for being prime.
40 
41 use strict;
42 use warnings;
43 
44 count_primes(10);
45 count_primes(1);
46 count_primes(20);
47 count_primes(100);
48 count_primes(1000);
49 count_primes(10000);
50 
51 sub count_primes {
52    my $max = shift;
53    my $primes = 0;
54    foreach my $num (1..$max) {
55       $primes += is_prime($num);
56    }
57    print "Input: $max\nOutput: $primes\n";
58 }
59 
60 {
61    my $cache;
62    sub is_prime {
63       my $num = shift;
64       return 0 if $num == 1;
65       return $cache->{$num} if defined $cache->{$num};
66       my $divider = 2;
67       while($divider <= sqrt($num)) {
68          if(int($num/$divider) == $num/$divider) {
69             $cache->{$num} = 0;
70             return 0;
71          }
72          $divider++;
73       }
74       $cache->{$num} = 1;
75       return 1;
76    }
77 }