Thread: Efficient Algorithm for counting number of factors

What is the most efficient algorithm for counting the number of factors of an integer?

It think that the 'policy' of every forum is that you post your code,thus your attempt of achieving what you are asking,and based on that improve the code!

Originally Posted by std10093

It think that the 'policy' of every forum is that you post your code,thus your attempt of achieving what you are asking,and based on that improve the code!

I agree with what you are saying....The thing is that I want to know if there exist some better algorithm than the straight approach of checking every number if its divisible from n=1 to N for a number N...Thats the most slowest approach I guess. I just need to know if you have any idea, because I need to apply that part to a program.

This is my small effort...It works but it will not fit into my program

Code:

int count_factors(int n)
{
    int i,f=1;
    if(n==1)
        return 1;
    else
    {
        for(i=2;i<=(n/2);i++)
        {
            if(n%i == 0)
               f++;
        }
        return (f+1);
    }

}

I am sure there are some better approach of finding upto square_root(n) and some recursive approach. Any ideas for that?? Just some discussion....I am not asking to write the code for me...

Oh,ok Well the first thing it comes to mind is that if you want to use sqrt then you have to load the library of math,which makes your program a bit slower.

Ok I see....using sqrt is not a much good choice then, but still using sqrt will save the time for other some useless looping,actually it will just balance the loading of libraries I guess....Whether using recursive approach is faster than the for loop??...Well I found some resources on wikipedia Integer factorization - Wikipedia, the free encyclopedia

But I am not much good in maths or the algorithm subject...some topics are going above the head

When having a problem we may solve it with a recursive algorithm or with an iterative one.When these two algorithms have the same complexity(=the actions done by them are of equal cost),then the iterative one is been selected.Why?Because recursion has the system to handle the stack with functions call etc. which is very expensive.

What the link says is that this problem is a heuristic.Also mind that it also says that non-efficient algorithms are found for these problem(when numbers are big.).
So you might want to take a look at this Fermat's factorization method - Wikipedia, the free encyclopedia

Ya right,recursion has to handle the stacks so extra consumption of resources....."An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure."---Haha, its already declared there does not still exist an efficient algorithm for that...It seems to find more I have to go more detail into the world of number theories and algorithms...

Especially Numerical Analysis and Algorithms and Complexity will give you a boost at these kind of things

This public domain library is stated as being the fastest code for finding factors, in the article you linked to:

Msieve | Free Security & Utilities software downloads at SourceForge.net

I'm not clear what you mean by your trial by division code "not fitting into your program"? It seems like a very small function, although it's also one of the slowest ways to find the factors.

A few notes on your trial by division code:

Code:

int count_factors(int n)
{
    int i,f=1,max;
    if(n==1)
        return 1;
    else
    {
        max=n/2+1;
        for(i=2;i<max;i++)
        {
            if(n%i == 0)
               f++;
        }
        return (f+1);
    }

}

Calculate the max value outside the for loop, so that value is calculated only one time. max=n/2+1 allows the slightly faster test of <, instead of <=.

If you can stop the inner loop at the square root of n, instead of n/2, by including math.h, then by all means, include math.h!

Again, make the calculation for max=sqrt(n)+1, just before the start of the for loop, so the calculation will only be made one time.

For VERY large prime numbers, you will be stuffed, of course. There is no known algorithm that will find all the factors of such numbers (and their related semi-primes), in a reasonable amount of time.

The main question is: What do your really want to calculate?

The code you've posted counts all divisors of a number, e.g. for 12 the result is 6 because 12 is divisible without a remainder by 1, 2, 3, 4, 6, 12

The rest of the posts talk about integer factorization which "is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer." (from the wikipedia article)
So for 12 the factors are 2x2x3 and counting all factors will result in 3.

So what do you want to do?

Bye, Andreas

Originally Posted by iMalc

Loading the math libe doesn't make it slower, or if you mean using sqrt, then that should not make it measurably slower either, as long as you only call it once, outside of the loop.

In big projects i agree,in very very very veeeeery small programs it does them slower because it is one more task for the system to do.

Originally Posted by AndiPersti

The main question is: What do your really want to calculate?

The code you've posted counts all divisors of a number, e.g. for 12 the result is 6 because 12 is divisible without a remainder by 1, 2, 3, 4, 6, 12

The rest of the posts talk about integer factorization which "is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer." (from the wikipedia article)
So for 12 the factors are 2x2x3 and counting all factors will result in 3.

So what do you want to do?

Bye, Andreas

Hello Andreas, what I want to do is count the number of factors f of a number and look if it is odd or even....It is a part of solving a programming question, well but it seems now that calculating the number of factors is quite lengthy and not an efficient approach...