Recursively counting divisors of a number

Question

I have a question, more on the theoretical side. I want to make a recursive function that counts all (not only prime) different divisors of a given natural number.

For example with f(0)=0 (per Def.), f(3) = 2, f(6) = 4, f(16) = 5 etc.

Theoretically, how could I do that?

Thanks.

Possible duplicate of [Algorithm to calculate the number of divisors of a given number](http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number) — Idos, Jun 16 '16 at 12:50
I think this question belongs to [mathoverflow](http://mathoverflow.net/) or another math SE community. — Willem Van Onsem, Jun 16 '16 at 12:52

FDavidov · Accepted Answer · 2016-06-17T08:53:15.907

If I understand correctly, you only want to COUNT them, not to collect them, right?

A second assumption is that you don't want to count only independent divisors (i.e. you want to count "2", "3" but not "6").

If this is the case, the algorithm shown in Sean's answer can be simplified significantly:

You don't need the array divisorList but only a counter,
You as soon as you find a divisor, you can reduce the max limit of the loop by the result of dividing the root number by the divisor (e.g. if your root number is 900 and 2 is the first divisor, you can set the limit of the loop to 450; then, when checking 3 you will reduce the limit to 150 and so on).

EDIT:

After thinking a little bit more, here is the correct algorithm:

Assume that the number is "N". Then, you already start with a count of 2 (i.e. 1 and N),
You then check if N divides by 2; if it does, you need to add 2 to the count (i.e. 2 and N/2),
You then change the limit of the loop to N/2,
Test if dividing by 3 yields an integer; if it does, you add 2 to the count (i.e. 3 and N/3) and reduce the limit to N/3,
Test 4...
Test 5...
...

In Pseudo-code:

var Limit = N ;

Count = 2 ;

for (I = 2 ; I < Limit ; I++) {

    if (N/I is integer) {

         Count = Count + 3 ;

         Limit = N / I ;

    } ;

} ;

Note: I don't know which language you are programming, so you need to verify if your language allows you to change the limit of the loop. If it does not, you can include an EXIT-LOOP condition (e.g. if I >= Limit then exit loop).

Hope this resolves your problem.

For example for 6,I want to count 1,2,3 and 6. So the function has to give me 4. Will the 2. of your answer work in this case? — vedsil, Jun 16 '16 at 14:39
I didn't engage into a mathematical proof, but I guess it will if you just add "2" (1 for "1" and one for "n") to the result I suggest. Let's see: take for instance 10. My result will yield 2 and 5, which is 2; you then add 2 getting 4. For 6: 2, 3 = 2, plus 2 = 4. I will leave for you to check for a higher number. Hope this is of help. — FDavidov, Jun 16 '16 at 19:15
Edited my answer with the correct (and extremely simple) algorithm. — FDavidov, Jun 17 '16 at 08:56

score 0 · Answer 2 · answered Jun 16 '16 at 12:54

0

public static ArrayList<int> recursiveDivisors(int num)
{
    ArrayList<int> divisorList = new ArrayList<int>();

    for (int i = 1; i <= num; i++)
    {   
        if (num % i == 0)
            divisorList.add(i)
    }
return divisorList;
}

Something like this? Returns all divisors in a divisor array list EDIT: Not recursive

answered Jun 16 '16 at 12:54

Sean

1,283
9
27
43

I need the count only, but it's not that important. But I cant figure out how to do it recursively. – vedsil Jun 16 '16 at 14:36
Simplest and dumbest answer ever!. you don't need to loop through all the elements. you can replace `i <= num` with `i*i <= num` or `i <= sqrt(num)`. The former is more efficient than the later I guess. – Diablo Dec 03 '20 at 09:12

Recursively counting divisors of a number

2 Answers2