Hi Derrick, On Wed, 03 May 2017 06:58:44 +0800 "derrick" <derr...@thecopes.me> wrote:
> Thank you for your complete answer. How much memory is used per array element? > In Perl, it can be quite a bit because an array contains a vector of pointer to "SV"s, and each SV may contain an integer, a string, a reference, a floating point number, etc. There's also the issue of memory fragmentation. You can mitigate some of that by using http://perldoc.perl.org/functions/vec.html or something like https://en.wikipedia.org/wiki/Perl_Data_Language . > I will work on a shorter algorithm. This one worked on shorter numbers so I > just used it for this. > By shorter do you mean 'faster in runtime speed'? There's also https://en.wikipedia.org/wiki/Code_golf . > Derrick > > > ------------------------------------------------------------------发件人:Jim > Gibson<jimsgib...@gmail.com>日 期:2017年05月03日 00:35:53收件人:derrick > cope<derr...@thecopes.me>; beginners<beginners@perl.org>主 题:Re: prime > factors > > 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 > > -- ----------------------------------------------------------------- Shlomi Fish http://www.shlomifish.org/ http://www.shlomifish.org/humour/Summerschool-at-the-NSA/ Buffy will always find a wooden stake to slay vampires, even if it means she will have travelled 100 years back in time, to plant a tree nearby. — http://www.shlomifish.org/humour/bits/facts/Buffy/ 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/