The middle challenge was to find the first prime Fibonacci number greater than 227000, add one to it, and then sum the prime numbers which were its factors. Here’s my first implementation:

sub is-prime($a) {
return Bool::True if $a == 2;
! [||] $a <<%%<< (2, 3, *+2 ... * > $a.sqrt);
}
my @fib := (1, 1, *+* ... *);
my $cutoff = 227000;
my $least-prime = 0;
for @fib -> $f {
next if $f <= $cutoff;
next unless is-prime($f);
$least-prime = $f;
last;
}
my $x = $least-prime + 1;
say [+] (2, 3, *+2 ... * > $x.sqrt).grep({ $x %% $^a && is-prime($a) });

Despite what seems like an obvious inefficiency (approximating the prime numbers with the odd numbers), this is pretty snappy, executing in 12.5 seconds.

I was planning to go on and talk about my new Math::Prime module here, but looking at this code, I think it can be expressed rather more nicely with a tweak or two here. Let’s see.

sub is-prime($a) {
return Bool::True if $a == 2;
! [||] $a <<%%<< (2, 3, *+2 ... * > $a.sqrt);
}
my @fib := (1, 1, *+* ... *);
my $cutoff = 227000;
my $least-prime = @fib.first({ $_ > $cutoff && is-prime($_) });
my $x = $least-prime + 1;
say [+] (2, 3, *+2 ... * > $x.sqrt).grep({ $x %% $^a && is-prime($a) });

So that’s what the `first`

method is good for!

I did indeed write Math::Prime just so I could use it here. It’s not a huge change from the previous version, really:

use Math::Prime;
my @fib := (1, 1, *+* ... *);
my $cutoff = 227000;
my $least-prime = @fib.first({ $_ > $cutoff && is-prime($_) });
my $x = $least-prime + 1;
say [+] (primes() ... * > $x.sqrt).grep({ $x %% $^a });

Unfortunately, Math::Prime isn’t optimized yet, and so this version, while a bit nicer, is actually slower than the previous version.

**Update:** With Moritz’s help I did some optimizations to Math::Prime, and the script using it is now very significantly faster than the others.

### Like this:

Like Loading...

*Related*

This entry was posted on October 20, 2010 at 2:20 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply