Hi Derrick,
Logically you are going with linear approach, better to find patterns that
can discard data that is not needed which will reduce time
I solved it while back using following algorithm of divide and break
sub largestPrimeFactors {
my $n = shift;
my $largest = 0;
# remove all factors divisible by 2
while ( $n % 2 == 0 ){
$largest = 2;
$n /= 2;
}
# loop till square root (see technique shared by Shlomi)
for (my $i = 3; $i <= int(sqrt($n)); $i += 2) {
while ($n % $i == 0) {
$largest = $i;
$n /= $i;
}
}
if ($n > 2) {
$largest = $n;
}
return $largest;
}
Hope it helps
On Tue, May 2, 2017 at 10:25 PM, Shlomi Fish <shlo...@shlomifish.org> wrote:
> Hi derrick!
>
> Welcome aboard!
>
> See below for my reply.
>
> On Tue, 02 May 2017 22:58:58 +0800
> "derrick cope" <derr...@thecopes.me> wrote:
>
> > I was writing a program to solve the #3 exercise on project Euler.
>
> For reference, it is https://projecteuler.net/problem=3 .
>
> >I needed
> > to find the prime factors of a given number. I have solved it already
> but a
> > couple of the ways I tried to solve the problem caused a problem.
> >
> > The below worked for smaller numbers but when I used the 12 digit number
> > given by project Euler I got "Out of memory!"
> >
> > chomp( my $factor = <>);
> > my @primefactor = grep { &isprime( $_ ) } ( grep { $factor % $_ == 0 }
> > 1..$factor );
>
> First of all, please go over http://perl-begin.org/tutorials/bad-elements/
> and
> avoid these bad elements. add 'use strict;' and 'use warnings;' and avoid
> calling subroutines with ampersands.
>
> In that line's case you're building several very long lists. In this case a
> foreach loop will be better. Also not that you can also write the nested
> greps
> as grep { $factor % $_ == 0 and isprime($_)} ... .
>
> >sub isprime {
> > my $numb = shift;
> > my @quot = grep {
> > if ( $numb % $_ == 0 ) {1;
> > } else { 0;}
> > } 2..$numb-1;
> > unless ( @quot ) {
> > 1;
> > # say "prime";
> > } else {
> > 0;
> > # say "not prime";
> > }
> > }
> >
>
> your indentation is lacking, and better see
> http://perl-begin.org/tutorials/bad-elements/#grep_instead_of_any . Also
> use
> an explicit return and don't use if or unless to return a value. (you can
> try
> using the ? : ternary conditional operator instead).
>
> >
> > This one worked but caused my computer to crash.
> > my $xxx = 1;
> > while ( $xxx < $factor ) {
> > if ( $factor % $xxx == 0 and &isprime($xxx) ) {
> > say $xxx;
> > }
> > $xxx++
> > }
> > what is causing perl to do this? Would using a module save
> memory?Thanks for
> > any help.
>
> That looks better memory wise. But "isprime()" is still sub-optimal.
>
> Note that you can optimise the algorithm considerably by using some
> tricks. See:
>
> https://duckduckgo.com/?q=project+euler+3&ia=web
>
> Perhaps see https://duckduckgo.com/?q=prime+factorization&ia=web too.
>
> Regards,
>
> Shlomi Fish
>
> --
> -----------------------------------------------------------------
> Shlomi Fish http://www.shlomifish.org/
> https://youtu.be/n6KAGqjdmsk - “Hurt Me Tomorrow”
>
> I love being convinced that I was wrong before. That way I knew I
> improved and am now wiser. Like the Klingon warriors say when it happens:
> “What a great day it was for me to die!”.
>
> Please reply to list if it's a mailing list post - http://shlom.in/reply .
>
> --
> To unsubscribe, e-mail: beginners-unsubscr...@perl.org
> For additional commands, e-mail: beginners-h...@perl.org
> http://learn.perl.org/
>
>
>
