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'
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!
 [reply] [d/l] [select] 

 [reply] 

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!
 [reply] [d/l] [select] 



 [reply] [d/l] 


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

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.
print "Just another Perl ${\(trickster and hacker)},"
The Sidhekin proves Sidhe did it!
 [reply] [d/l] [select] 

 [reply] 
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.
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  [reply] [d/l] 
Re: Finding all divisors of an integer by gri6507 (Deacon) on Jul 03, 2004 at 14:08 UTC 
Crocodil GenaThis 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.  [reply] 

 [reply] 

This algorithm finds all factors of a number!
 [reply] 

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...
 [reply] 
Re: Finding all divisors of an integer by pbeckingham (Parson) on Jul 03, 2004 at 15:36 UTC 
 [reply] 
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.  [reply] 
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";
 [reply] [d/l] 
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";
 [reply] [d/l] 

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);
}
 [reply] [d/l] 

