Lopez

patterns . logic . reason . empathy . the golden rule

I’ve been toying around with functional programming, and recently came across a perlmonks thread discussing multiple ways to calculate prime numbers. One of the things I noticed about many of the examples was that almost all of them used loops of some sort (for, when, etc). So I decided to tackle the problem without using any loops. Instead, I’ll just use recursive functions.

Firstly, here’s the perlmonks thread: Prime Number Finder

And here’s the solution I came up with:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #!/usr/bin/env perl use strict; use warnings; use 5.010; $DB::deep = 500; $DB::deep = $DB::deep; # Avoids silly 'used only once' warning no warnings "recursion"; # Identify primes between ARG0 and ARG1 my ($x, $y, $re_int, $result); my ($prime, $is_int); $x = $ARGV[0]; $y = $ARGV[1]; $is_int = sub { my $re_int = qr(^-?\d+\z); my ($x) = @_; $x =~ $re_int ? 1 : 0; }; $prime = sub { my ( $x, $y ) = @_; if ( $y > 1 ) { given ($x) { when ( $is_int->( $x / $y ) ) { return 0; } default { return $prime->( $x, $y - 1 ); } } } else { return 1; } }; $result = sub { my ( $x, $y ) = @_; if ( $x <= $y ) { if ( $prime->($x, $x-1) ) { say $x; } $result->( ( $x + 1 ), $y ); } }; $result->($x, $y); |

When running this code with larger numbers, I would eventually run into “deep recursion” warnings, which is why I’ve had to use `no warnings "recursion";`

and set $DB::deep to a specific value higher than 100 (which is the default). $DB::deep is a debugging variable used specifically to limit recursion depth, in order to prevent long-running or infinite recursive operations.

The method I’m using here to calculate prime numbers isn’t the most efficient, since I’m not doing anything to reduce the amount of numbers I have to test at each cycle. However, adding some extra intelligence to this, such as the filtering used by the Sieve of Eratosthenes (an “ancient Greek algorithm for finding all prime numbers up to a specified integer.”) should be doable.

I’ll be keeping an eye out for other solutions, since I’m sure there are many (especially in perl), but so far this one seems to be fairly fast and clean. I’m looking forward to what Math::BigInt can offer here as well, if anything.

## Comments