Perl Monk, Perl Meditation PerlMonks

Finding all divisors of an integer

 on Jul 03, 2004 at 13:53 UTC 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 : ";
print "Enter the little number : ";
\$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";

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!

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

so i need to know this \$i...

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

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!

how?
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
```#!/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);
}

Create A New User
Node Status?
node history
Node Type: perlquestion [id://371576]
Approved by neniro
help
Chatterbox?
 [Corion]: Mwahahaha - it looks as if \$work will soonish be looking for a programmer (not to be employed by IT) to maintain some code, partly by me. Maybe even in Perl.

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2018-05-24 14:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (178 votes). Check out past polls.

Notices?