Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Finding all divisors of an integer

by chiburashka (Initiate)
on Jul 03, 2004 at 13:53 UTC ( [id://371576]=perlquestion: print w/replies, xml ) Need Help??

chiburashka has asked for the wisdom of the Perl Monks concerning the following question:

is there a fast way to tell all the numbers that a spesific number divides on without leftovers (like for the spesific number "20" it divedes on 1,2,4,5,10,20 and stays as an integer) ? How to find those "1,2,4,5,10,20" in the fastest way ?

that's my code :

#!/usr/bin/perl use Math::BigInt; print "Enter the big number : "; $x = readline(*STDIN); print "Enter the little number : "; $y = readline(*STDIN); $z = $x - $y; $i = $z; @all = ''; $j = 0; system cls; ($sec,$min,$hour,$mday,$mon,$year,$wday,$yday) = gmtime(time); while ($i ne 0) { $t = $z / $i; $k = Math::BigInt->new($t); $k = $k->is_int(); if ($k eq "1") {$j++; $all[$j] = "$t\n";} $i--; print "$i\n"; } ($sec1,$min1,$hour1,$mday,$mon,$year,$wday,$yday) = gmtime(time); $data="Dis.txt"; open(DAT, $data) || die("Could not open file!"); @al=<DAT>; @al = @all; open(DAT,">$data") || die("Cannot Open File"); print DAT @al; close(DAT); print "@all It took ", $min1 - $min, " minuts!\n"; $w = readline(*STDIN);

now how to make it find those numbers FASTER ?

20040705 Edit by castaway: Changed title from 'Didision'

Replies are listed 'Best First'.
Re: Finding all divisors of an integer
by Sidhekin (Priest) on Jul 03, 2004 at 14:01 UTC

    For small numbers, this should be straightforward ...

    @divisors = grep { $number % $_ == 0 } 1 .. $number;

    I would not worry about optimizing this, unless you need it for very many or very big numbers ... but then it would be something like this:

    # First, the lower half of the divisors: @divisors = grep { $number % $_ == 0 } 1 .. sqrt($number); # Then, the upper half: push @divisors, map {$number == $_*$_ ? () : $number/$_} reverse @divi +sors;

    (Sorry, I missed the Math::BigInt stuff ... but I guess the algorithm above can be adapted to that case as well?)

    Update: Most of my code could benefit from comments. I added comments to the optimized version. Never code as if the guy who ends up maintaining your code can always maintain a proper caffeine intake.

    print "Just another Perl ${\(trickster and hacker)},"
    The Sidhekin proves Sidhe did it!

      Sidhekin,
      I would not worry about optimizing this, unless you need it for very many or very big numbers
      Indeed, the node was updated after you (and I) already started posting. I would say that you only need to go to $number / 2 though.

      @divisors = grep { $number % $_ == 0 } 1 .. sqrt($number);
      I think you are thinking of prime factorization here. You can stop there to determine primeness but not to determine all factors.

      Cheers - L~R

      People should not be allowed to touch keyboards early in the morning (weekend) without proper caffeine intake. I completely missed the push in the second line of code

        @divisors = grep { $number % $_ == 0 } 1 .. sqrt($number);
        I think you are thinking of prime factorization here. You can stop there to determine primeness but not to determine all factors.

        You somehow miss the second line of my optimized solution. It adds the other half of the divisors. :-)

        push @divisors, map {$number == $_*$_ ? () : $number/$_} reverse @divi +sors;

        For every divisor above the square root, there is a corresponding divisor below the square root. Symmetrical optimization. :-)

        print "Just another Perl ${\(trickster and hacker)},"
        The Sidhekin proves Sidhe did it!

        A reply falls below the community's threshold of quality. You may see it by logging in.
      A reply falls below the community's threshold of quality. You may see it by logging in.
    A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Finding all divisors of an integer
by Limbic~Region (Chancellor) on Jul 03, 2004 at 14:05 UTC
    chiburashka,
    My solution will likely not win the "fastest way" solution. There are likely CPAN modules that do this as well. Usually when someone wants the fastest way to do something - they are taking the wrong approach or using the wrong language. Perhaps if you don't get the answers you like you should expand on the overall picture.
    #!/usr/bin/perl use strict; use warnings; my @factors = Factor_It( 20 ); print "$_\n" for @factors; sub Factor_It { my $number = shift; my @factors; for ( 2 .. int $number / 2 ) { push @factors, $_ unless $number % $_; } return (1, @factors, $number); }
    Of course, you will also want to add some checks to ensure your input is a positive whole integer greater than 1.

    Cheers - L~R

    It looks like you updated your node after you posted it with the BigInt stuff - probably want a CPAN module with XS code. You can avoid checking even numbers if it is not evenly divisible by 2 on the first check
Re: Finding all divisors of an integer
by gri6507 (Deacon) on Jul 03, 2004 at 14:08 UTC
    Crocodil Gena

    This sounds like a homework problem. Yet nonetheless, let me give a shot at answering your question. Basically what you are asking for is an algorithm that finds the smallest prime number a given number is divisible by (except for the multiplicative identity). So, in your case, the smallest prime that 20 is divisible by is 2, giving your a remainder of 10. The smallest prime 10 is divisible by is, again, 2, giving you a remainder of 5. Five, in itself is prime, so you're done.

    So, 20 is made up of 2,2,5, and of course the multiplicative identity. Multiplying together the different combinations of the found primes, gives you the factors you were asked to find.

      That's not at all the question that is being asked, and has nothing to do with primes. OP is asking for factorization all factors of a number.

        This algorithm finds all factors of a number!
        If you multiply all the possible combinations of the prime factors together (and get rid of repeats), you get a list of all the factors, and the number itself. I wonder how you multiply all the possible combinations of a list...
Re: Finding all divisors of an integer
by pbeckingham (Parson) on Jul 03, 2004 at 15:36 UTC

    Only numbers up to the square root of the large number need to be checked - not half.

Re: Finding all divisors of an integer
by gaal (Parson) on Jul 03, 2004 at 14:08 UTC
    The process you are asking about is called factorization in mathematics. Depending on what you call fast, there may not be a really fast method for factoring large numbers.
Re: Finding all divisors of an integer
by neniro (Priest) on Jul 03, 2004 at 14:06 UTC
    It's already answered, so my solution is obsolete.
    #!/usr/bin/perl use strict; use warnings; chomp(my $is = shift); for (1 .. $is) { print "$_ " if ($is % $_ == 0); } print "\n";
Re: Finding all divisors of an integer
by ysth (Canon) on Jul 04, 2004 at 08:29 UTC
    Here's an implementation of gri6507's suggestion (using ordinary perl integers, not bigints):
    use warnings; use strict; use integer; $|=1; print "Enter number: "; chomp(my $x = <STDIN>); die "That's not my kind of number!" if $x=~/\D/ || $x/1 ne $x; if ($x <= 1) { print "$x\n"; exit } # get prime factors my %fact; my $fact = 2; do { ++$fact while $x/$fact*$fact != $x; ++$fact{$fact}; $x /= $fact; } while ($x > 1); # apply all combinations my @fact = 1; while (($fact,my $count) = each %fact) { my $index; @fact = map $_ * $fact**(++$index/@fact % ($count+1)), (@fact) x ($count+1); } print "@{[sort {$a<=>$b} @fact]}\n";
      oi? Newbie programer here.. dividing the number for primefactorization? sounds like this subroutine i cooked up to do my homework...
      sub primefactor ($) { my $number=shift; my @factors=(); for (my $i=2; $i<=$number;) { unless ($number%$i) { $number/=$i; push @factors, $i; } else {$i++} } @factors&&return(@factors); return($number); }

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://371576]
Approved by neniro
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (5)
As of 2024-03-29 14:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found