patterns . logic . reason . empathy . the golden rule

» Playing With Prime Numbers

Computing . Perl . Personal
10-October, 2011 by

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

Leave a Reply

Your email address will not be published. Required fields are marked *


9 − = one


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Next | Previous
Theme made by Igor T. | Powered by WordPress | Log in | Register | RSS | Back to Top