> On May 2, 2017, at 7:58 AM, derrick cope <derr...@thecopes.me> wrote:
>
> I was writing a program to solve the #3 exercise on project Euler. 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.
Exercise #3 is to find the largest prime factor of the number 600,851,475,143.
>
> 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 );
Presumably, you have entered the number 600851475143 into the command line that
executes your program. Therefore, $factor is equal to 600851475143 and the
expression 1..$factor will be a list of 600851475143 elements; ( 1, 2, 3, … ,
600851475143 ). You will need a computer with several petabytes of memory to
store that list.
>
> 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";
> }
> }
This function also generates a very long list of integers (2..$numb-1).
>
>
> 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.
Using a module would not save significant memory. You need to devise an
algorithm that does not require long lists of numbers. You need to test each
potential prime factor one at a time. You will also need to address the fact
that Perl’s integers cannot represent the number 600851475143 in their normal
32- or 64-bit formats. See ‘perldoc bignum’.
Also note that the smallest factor of any number cannot be larger than the
square root of that number, so the function isprime need not consider potential
factors larger than the square root of its argument.
Jim Gibson
--
To unsubscribe, e-mail: beginners-unsubscr...@perl.org
For additional commands, e-mail: beginners-h...@perl.org
http://learn.perl.org/
