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; Originally Posted by rakeshkool27 Thanks Adak....for the suggestion of your calculating one time, I did not notice that....I mean by ...

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by rakeshkool27 View Post
    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...
    Oh, I know the feeling!! About a year ago, I was trying to solve a problem that was EXTREMELY run-time critical, involving prime numbers. It was REALLY driving myself and a couple friends, batty - finally, brought it up on this board, and KCfromNC showed me a buffering trick with the screen buffer that made all the difference.

    On this forum, we've been known to go completely "bonkers" with an efficiency focus on a number of problems. Many trivial and funny, but some were quite large and anything but trivial.

    Before anything more substantial however, we need to know the details:

    1) What is the EXACT problem and all the constraints!

    2) What run-time are you getting now, and with what kind of system hardware? Usually, cpu and it's system speed will do.

    The hardware it's being run on is critical! For instance, my prime number problem had to run on an OLD Intel cpu @850MHz, for it's test!

    Anyway, you have people here who are VERY concerned with run-time efficiency, and actually REVEL in solving problems related to it.

    So, cough it up, buddy!

  2. #17
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by iMalc View Post
    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.
    No,i am not.Please do not call me like this.I just remember that when i first starting coding,we had to write some code to calculate the carmichael numbers.It was a small piece of code and the test was on Linux.That's why i stated out,because rakeshkool27 may use linux

    PS- i agree with you

  3. #18
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by rakeshkool27 View Post
    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...
    Just to be sure: if I call your function from post #3 for 12 I get the return value 6. So you are interested in all possible divisors/factors, correct?

    Then you have to test if the number is a square number because
    Quote Originally Posted by Wikipedia
    Another property of a square number is that it has an odd number of divisors, while other numbers have an even number of divisors. An integer root is the only divisor that pairs up with itself to yield the square number, while other divisors come in pairs.
    java - Fastest way to determine if an integer's square root is an integer - Stack Overflow

    Bye, Andreas

  4. #19
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    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.
    Which is balanced by the number of tasks you eliminate by looping up to the sqrt rather than up to n/2. It's not like mod of an arbitrary integer is a cost-free operation in itself, so if you eliminate lots of mods in exchange for a single sqrt call it's a net win.

  5. #20
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,501
    I'm guessing that it's problem 12 from projecteuler.net -> The reason is that I'm having the same runtime problems

    The idea is to find the first number with 500 integer factors

    I wrote a routine that works great for finding lower amount of factors, but as soon as I search for something big, my routine is just not efficient enough to return a value in a realistic time.

    Right now I am approaching the problem by making a Sieve of Eratosthenes to get all the primes and approaching the problem with the method described here: how many factors?.

    Getting factors from big numbers is time consuming - I suppose that's why Crypo uses it so much

    If this doesn't work for me, I'll be starting a new thread.

    I hope this helps

  6. #21
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,501
    OK... I re-read the problem (always helps) - and the question asked for the first Triangle number that has over 500 factors. I solved the problem VERY quickly after that.

    I hope my method for solving integer factors in my last post helps the OP

  7. #22
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by Adak View Post
    Oh, I know the feeling!! About a year ago, I was trying to solve a problem that was EXTREMELY run-time critical, involving prime numbers. It was REALLY driving myself and a couple friends, batty - finally, brought it up on this board, and KCfromNC showed me a buffering trick with the screen buffer that made all the difference.

    On this forum, we've been known to go completely "bonkers" with an efficiency focus on a number of problems. Many trivial and funny, but some were quite large and anything but trivial.

    Before anything more substantial however, we need to know the details:

    1) What is the EXACT problem and all the constraints!

    2) What run-time are you getting now, and with what kind of system hardware? Usually, cpu and it's system speed will do.

    The hardware it's being run on is critical! For instance, my prime number problem had to run on an OLD Intel cpu @850MHz, for it's test!

    Anyway, you have people here who are VERY concerned with run-time efficiency, and actually REVEL in solving problems related to it.

    So, cough it up, buddy!
    Hey Adak sorry for replying late, (actually was involved with some exam studies)...oh good to know that you also tried this problem before...as I said it was a part of a programming question and the question is not directly involved with finding out the factors, actually the logic of finding out the factors of an integer is the main part of solving the question....You may see the problem here Doors | CodeChef
    Well you can see the constraints. So I had two approaches to try the problem. Both the approaches I thought exceeded the time limit and the contest is over now. The first approach was straight and it was much efficient. The second approach involved factoring of numbers and it took more time than the first approach,so I discarded it. I could not think any better approach than those and its an interesting problem to solve.

  8. #23
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by AndiPersti View Post
    Just to be sure: if I call your function from post #3 for 12 I get the return value 6. So you are interested in all possible divisors/factors, correct?

    Then you have to test if the number is a square number because


    java - Fastest way to determine if an integer's square root is an integer - Stack Overflow

    Bye, Andreas
    Yeah Andreas it was finding the no. of divisors or factors of a number. You put up some interesting fact about the square number....Well I have left that factoring approach. Its not efficient thats why. Well thanks for answering....You can see the question here and its interesting-- Doors | CodeChef

  9. #24
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You're right, that's a fun problem -- shame on you for not replying before the contest was over!!

    A perfect binary problem.

  10. #25
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by Click_here View Post
    I'm guessing that it's problem 12 from projecteuler.net -> The reason is that I'm having the same runtime problems

    The idea is to find the first number with 500 integer factors

    I wrote a routine that works great for finding lower amount of factors, but as soon as I search for something big, my routine is just not efficient enough to return a value in a realistic time.

    Right now I am approaching the problem by making a Sieve of Eratosthenes to get all the primes and approaching the problem with the method described here: how many factors?.

    Getting factors from big numbers is time consuming - I suppose that's why Crypo uses it so much

    If this doesn't work for me, I'll be starting a new thread.

    I hope this helps
    hey Click_here, your link was quite useful...It put me into a moment to think...It is the correct approach to find the number of factors. My problem is not linked with projecteuler, actually here is the link Doors | CodeChef

  11. #26
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by Adak View Post
    You're right, that's a fun problem -- shame on you for not replying before the contest was over!!

    A perfect binary problem.
    Hehe....dont worry...There is always a contest every month, you will get to solve more....There is more to come this 1st of September...

Page 2 of 2 FirstFirst 12
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, 09:06 AM
  2. efficient compression algorithm pls
    By gooddevil in forum C Programming
    Replies: 7
    Last Post: 05-08-2004, 04:33 AM
  3. Find all factors of a number
    By Spono in forum C Programming
    Replies: 5
    Last Post: 10-23-2003, 02:23 AM
  4. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 03:01 PM
  5. function to determine factors of a number
    By lakai02 in forum C Programming
    Replies: 2
    Last Post: 12-18-2002, 03:02 AM

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