PWC146 - 10001st Prime Number

TL;DR

Here we are with TASK #1 from The Weekly Challenge #146. Enjoy!

The challenge

Write a script to generate the 10001st prime number.

The questions

Citing this tweet:

There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors.

So I have a meta question: is this a plot by Colin Crain to get rid of a lot of solutions with a technical error? And yet it’s difficult to ignore that there’s a whole page on the problem at rosettacode.org, with plenty of solutions and ways to check the result.

The solution

The Raku solution is a variation over the code in rosettacode.org:

#!/usr/bin/env raku
use v6;
sub MAIN (Int:D $n where * > 0 = 10001) {
   ((1 .. *).grep: *.is-prime)[$n - 1].put
}

TIL that lazy ranges are way more efficient than lazy sequences, at least as of v.6d.

Perl requires some more effort because the primality test is not included (they had to choose between it and the batteries, I think):

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

say prime_at(shift // 10001);

sub prime_at ($n) {
   state $primes  = [ undef, 2, 3 ];
   state $squares = [ undef, 4, 9 ];
   FIND_NEW:
   while ($primes->$#* < $n) {
      my $candidate = $primes->[-1] + 2;
      while ('necessary') {
         for my $i (2 .. $primes->$#*) {
            if ($squares->[$i] > $candidate) {
               push $primes->@*, $candidate;
               push $squares->@*, $candidate * $candidate;
               next FIND_NEW;
            }
            last unless $candidate % $primes->[$i];
         }
         $candidate += 2;
      }
   }
   return $primes->[$n];
}

We’re using the primes computed “so far” to check for the new ones. We’re also keeping the squares of those computed primes around, because they help to understand when to stop “prematurely” with the search.

Cheers and stay safe, folks!


Comments? Octodon, , GitHub, Reddit, or drop me a line!