Thread: Efficient Algorithm for counting number of factors

Originally Posted by rakeshkool27

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!

Originally Posted by iMalc

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

Originally Posted by rakeshkool27

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

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

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.

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.

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

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

Originally Posted by Adak

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.

Originally Posted by AndiPersti

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

You're right, that's a fun problem -- shame on you for not replying before the contest was over!!

A perfect binary problem.

Originally Posted by Click_here

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

Originally Posted by Adak

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...