Like Tree1Likes

Efficient Algorithm for counting number of factors

This is a discussion on Efficient Algorithm for counting number of factors within the C Programming forums, part of the General Programming Boards category; What is the most efficient algorithm for counting the number of factors of an integer?...

  1. #1
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105

    Efficient Algorithm for counting number of factors

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

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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. #3
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by std10093 View Post
    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. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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. #5
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    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. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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. #7
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    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. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Especially Numerical Analysis and Algorithms and Complexity will give you a boost at these kind of things

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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
    stahta01 likes this.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Quote Originally Posted by std10093 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by iMalc View Post
    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. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Quote Originally Posted by std10093 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    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...
    Last edited by rakeshkool27; 08-24-2012 at 09:23 PM.

  15. #15
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by AndiPersti View Post
    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...

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Efficient Sorting Algorithm
    By GCNDoug in forum C++ Programming
    Replies: 10
    Last Post: 11-13-2008, 08:06 AM
  2. efficient compression algorithm pls
    By gooddevil in forum C Programming
    Replies: 7
    Last Post: 05-08-2004, 03:33 AM
  3. Find all factors of a number
    By Spono in forum C Programming
    Replies: 5
    Last Post: 10-23-2003, 01:23 AM
  4. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 02:01 PM
  5. function to determine factors of a number
    By lakai02 in forum C Programming
    Replies: 2
    Last Post: 12-18-2002, 02:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21