# Thread: Efficient Algorithm for counting number of factors

1. ## Efficient Algorithm for counting number of factors

What is the most efficient algorithm for counting the number of factors of an integer? 2. 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!  3. 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... 4. 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. 5. 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 6. 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 7. 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... 8. Especially Numerical Analysis and Algorithms and Complexity will give you a boost at these kind of things  9. This public domain library is stated as being the fastest code for finding factors, in the article you linked to:

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. 10. 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 11. Originally Posted by std10093 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.
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. 12. 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. 13. Originally Posted by std10093 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.
Oh, you must be one of those people who use Linux and time things by getting the actual user and kernel mode duration reported. See we Windows people don't do that; A couple extra milliseconds isn't something a user will notice. 14. Thanks Adak....for the suggestion of your calculating one time, I did not notice that....I mean by saying not fitting into my program means that I am trying to solve a question and it gives certain time constraint, and finding the factor is a crucial part in solving the problem...so the trial division definitely doesn't fit here, thats what i meant. Well it seems now that the factor finding approach for the solution to the problem is not going to give much help....its consuming a lot time... 15. 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... Popular pages Recent additions 