# Multiple and divisors

A number A is said to be multiple of B if there is an integer n such that

$A = nB$

And so far I think my grandmother knew it, too.

But from this definition you directly revenue that B is a divisor of a is not always so intuitive. Seen on the contrary in fact, B is contained a number n integer of times in A.

`$A = nB$`

In programming, you can check this property (of B to be and A divisor) by using the module operator %, which returns the remainder of a division between integers. From the definition of the first follows that a number B is said A divisor if the remainder of the division of A for B is 0.

`$A \mod B = 0$`

### `Now you try`

Choose A and B as you prefer and check the reminder of the division.

```<?php

function reminder(\$A, \$B) {
\$r = \$A % \$B;

return \$r;
}

\$IN = (array) json_decode(base64_decode(\$argv[1]));
extract(\$IN);
echo reminder(\$A, \$B);
?>```

```{
"A": 6,
"B": 2
}```
`0`

## All divisors of a number

Divisors $d_i$ of a number N are all numbers that, if divided by N give remainder 0. To find them we can scroll all the numbers from 1 to N. If N is very large, the time needed to run our program could be very high, since its complexity is O(n).

We can then reason in another way: we find the first factors of N, we save all the powers of each factor (in the breakdown in prime factors that is done in the middle) and from there we have the table from which to calculate the divisors, as produced between all the combinations of powers found.

### `Now you try`

Choose `1 < N < 108` and find all divisors

```<?php

function divisors(\$N) {
\$p = []; //Mapping of the powers of the prime dividers of \$N. Es. \$p[2] = 2, 4, 8
\$j = 2; //Divisor test

//Copy of \$N. It is not Necessary to lose track of the initial number.
\$q = \$N;

while(\$j <= sqrt(\$q)) {
\$x = 1; //First exponent of the divisor

//If it is a divisor
while(!(\$q % \$j)) {
//Divide by divisor
\$q /= \$j;

//p[prime factor] = [array of x powers 0..p^x]
\$p[\$j][] = \$j**(\$x++);
}
\$j++;
}

if (\$q > 1) \$p[\$q][] = \$q;

/*Dp will contain the \$N dividers by way
Pp contains all \$p powers, the first factor of \$N
To obtain each divider, you have to multiply by each power \$Pp all the divisors already calculated of \$Dp. This will generate a new list of divisors to be saved in Dp.
*/
\$Dp = [1];

foreach (\$p as \$Pp) {
foreach(\$Dp as \$dp){
foreach (\$Pp as \$pp) {
\$d = \$dp*\$pp; //nuovo divisore
if (\$d <= \$N) \$Dp[] = \$d;
}
}
}
//I Order the factors from the smallest to the largest
sort(\$Dp);
return \$Dp;
}

\$IN = (array) json_decode(base64_decode(\$argv[1]));
extract(\$IN);
\$divisors = divisors(\$N);

echo implode("\n", \$divisors);

?>```

#### JSON-formatted Input

```{
"N": 20
}```
```1
2
4
5
10
20```

It may seem more complex as a method, however on large numbers it greatly decreases the necessary computing power. This is because the three nested loops contain few elements.