Thank
you.------------------------------------------------------------------发件人：Shlomi
Fish<shlo...@shlomifish.org>日 期：2017年05月04日
03:27:03收件人：derrick<derr...@thecopes.me>抄 送：Jim Gibson<jimsgib...@gmail.com>;
beginners<beginners@perl.org>主 题：Re: prime factorsHi 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 .
