Here is a PDL implementation but it runs in about 5mins
on my cygwin/win7 system and uses a lot of memory. The
real performance killer for PDL is the allocation and
creation of new PDLs. The computations are much faster
then the plain perl ones. How does this run on your Mac?
#!/usr/bin/env perl
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
# use POSIX qw(floor);
# Problem 3:
# The prime factors of 13195 are 5, 7, 13, 29.
# What is the largest prime factor of 600851475143 ?
my $num = 600851475143;
#my $num = 13195;
my $m = floor(sqrt($num));
print "max factor limit: $m\n";
# solve using sieve of erastothenes
my @primes = ();
my $possible = indx(2 .. $m);
my $cnt = 0;
while (any $possible) {
my $p = $possible((0));
$possible = where $possible, $possible % $p;
push @primes, $p;
#print "Remaining: ", $possible->nelem, "\n";
#print "Found possible prime factor: $p\n";
}
my $factors = indx(@primes);
$factors = where $factors, $num%$factors==0;
if (any $factors) {
print "Prime Factors of $num: $factors\n";
} else {
print "$num is prime\n";
}
Cheers,
Chris
On 2/14/2015 13:27, Vikas N Kumar wrote:
Hi
I am just casually solving some Project Euler problems using Perl.
For problem 3 (https://projecteuler.net/problem=3) I solved it using
the code below. The problem is stated in the code comments.
The code is single threaded and takes about 5-10 minutes on a standard
Intel i5 CPU on a 3 year old Macbook Air.
Can PDL make this faster ? No bignums are being used.
#!/usr/bin/env perl
use strict;
use warnings;
use POSIX qw(floor);
# Problem 3:
# The prime factors of 13195 are 5, 7, 13, 29.
# What is the largest prime factor of 600851475143 ?
my $num = 600851475143;
my $m = floor(sqrt($num));
print "max factor limit: $m\n";
# solve using sieve of erastothenes
#
my @primes = ();
my @possible = (2 .. $m);
while (@possible) {
my $p = shift @possible;
@possible = grep { $_ % $p != 0 } @possible;
push @primes, $p;
print "Remaining: ", scalar(@possible), "\n";
print "Found possible prime factor: $p\n";
}
my @factors = grep { $num % $_ == 0 } @primes;
if (@factors) {
print "Prime Factors of $num: ", join(",", @factors), "\n";
} else {
print "$num is prime\n";
}
_______________________________________________
Perldl mailing list
Perldl@jach.hawaii.edu
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
