Finding all divisors of an integer

[chiburashka]

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'

[Sidhekin]

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.

[chiburashka]

and how will i know how many numbers are in @divisors in the second case ?

[Sidhekin]

and how will i know how many numbers are in @divisors in the second case ?

Well, this is basic Perl. To quote perldata:

If you evaluate an array in scalar context, it returns the length of the array.

So, scalar(@divisors) returns the number of divisors.

[Anonymous Monk]

how?

[Limbic~Region]

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.

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

[chiburashka]

i simply want to make each $divisors[$i] = "$divisors[$i]\n";

so i need to know this $i...

[Sidhekin]

@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. :-)

[Limbic~Region]

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. 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

[neniro]

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";

[gaal]

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.

[gri6507]

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.

[pbeckingham]

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.

[gri6507]

This algorithm finds all factors of a number!

[Anonymous Monk]

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...

[pbeckingham]

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

[ysth]

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";

[Anonymous Monk]

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);
}