I made my own attempt at a solution (attached).
It runs in 6s in a Dell Inspiron N5110 and in 53s in an ASUS
Transformer tablet. So I guess it is fast. It seems correct but I have
some doubts (below)
------------------------------ Code:
#!/usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use POSIX 'floor';
use PDL::Lite;
use PDL::NiceSlice;
my $num=$ARGV[0];
my $max=floor(sqrt($num));
my $possible=PDL->sequence($max+1);
$possible->((1)).=0;
foreach(2..$max/2) {
next unless $possible->(($_));
$possible->(2*$_:-1:$_).=0;
}
my $primes=$possible->where($possible);
my $factors;
my $allfactors=PDL->zeros(0);
my $n=$num;
do {
$factors=$primes->where($n%$primes==0);
$n/=$factors->prod;
$allfactors=$allfactors->append($factors);
} while $factors->nelem;
$allfactors=$allfactors->append($n) unless $n==1;
say $allfactors->qsort;
Output: -----------------------------------------
mochan@yapaque:~/txt/cache/15/scratch$ time ./erastotenes.pl 600851475143
[71 839 1471 6857]
real 0m6.148s
user 0m6.132s
sys 0m0.012s
----------------------------------------
The do loop is to catch the multiplicity of the prime factors.
There is something strange though. I suspect my system has errors when
calculating moduli, as the factor 71 was the last found instead of
being the first. When I ran with the debugger I got this strange
result:
DB<9> p $primes->slice('(19)') #get the suspect prime position
71
DB<10> p $num%71 #71 divides $num, 600851475143
0
DB<11> p $num%$primes->slice('(19)')
753322814151
I expected to obtain zero here, as $primes->slice('(19)')==71, but
instead I obtained 753322814151. So it seems that pdl and perl yield
different results! Could it be due to using default types?
Best regards,
Luis
On Sun, Feb 15, 2015 at 04:03:45PM -0500, Chris Marshall wrote:
> Yes, maybe some use of ->sever to turn off data flow
> might allow things to be freed. It is definitely
> possible to tend the memory directly in the implementation
> to work around the alloc/free issue.
>
> --Chris
>
> On 2/15/2015 08:32, Vikas N Kumar wrote:
>
> Chris, this blows up the memory on my Macbook Air and fills up all the
> swap
> space (clearly there isn't much) and i had to restart the system to
> recover
> it.
> The pure perl version is more efficient due to possible perl
> optimizations.
>
> So the culprit is the "$possible = where $possible, $possible % $p; "
> line.
> There are way too many PDL objects being created and none of them being
> freed.
>
> Here is a more efficient C-based solution that I thought of:
> I was thinking of a way to store the integers in a bitmap stream of bytes
> where the integer value is just an index into a bitmap of 0's and 1's.
>
> When the integer is composite or divisible by anything other than itself,
> it's bit can be flipped to 0. So in the end all the primes will be all the
> bits that are 1, whose indexes can then be collected.
>
> I am not sure if I can do this in PDL.
>
> It isn't necessary to.
> Thanks for your program.
>
> --Vikas
>
> On 02/14/2015 05:27 PM, Chris Marshall wrote:
>
> 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
> [email protected]
> http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
--
o
W. Luis Mochán, | tel:(52)(777)329-1734 /<(*)
Instituto de Ciencias Físicas, UNAM | fax:(52)(777)317-5388 `>/ /\
Apdo. Postal 48-3, 62251 | (*)/\/ \
Cuernavaca, Morelos, México | [email protected] /\_/\__/
Consider using GnuPrivacyGuard https://www.gnupg.org/
My key: 791EB9EB, C949 3F81 6D9B 1191 9A16 C2DF 5F0A C52B 791E B9EB, yours?
_______________________________________________
Perldl mailing list
[email protected]
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
