Counting divisors

[sequba]

I need a very fast way of counting the divisors of very large number.

I've written something like that, but it's to slow for me:

unsigned long int number = 273949374;

unsigned int divisors = 2;
for(unsigned long int i=2 ; i <= (number>>1) ; i++)
		{
			if(!(number%i)) divisors++;
		}	

Probably there is some way using prime factors, but i'm not sure.
Thanks for any help.

[wasabi]

The answer to that question is the hacker's delight.

There is no simpler solution to that question. Just go for the for-loop until number/2.

for(int i=2;i<number/2;i++)
   if(!number%i)
      cout << number << "is divisible by" << i;

[helios]

sqrt(number) is much faster (specially for large n).

[ne555]

You just need the primes divisors.
Later you do combinatory on the exponents of the primes factors

[sequba]

There is no simpler solution to that question. Just go for the for-loop until number/2.

...

That's exactly, what i have...

I need to know only the number of divisors, I do not need to know those divisors...

You just need the primes divisors.
Later you do combinatory on the exponents of the primes factors

But how?
Can you write it for me?

[ne555]

suppose that your number is 5040, and you factorise it
5040 = 2⁴ * 3² * 5 * 7
The number of divisors will be
N_Divisors = 5 * 3 * 2 * 2 = 60 (note that I add 1 to every exponent)


To factorise you can do something like this

for(K = 0; K<prime.size() && prime[K] * prime[K] <= n; K++){
   while(n%prime[K] == 0){ 
      n/=prime[K];
      //...
   }
   //...
}
//here n is 1 or a prime number 

[sequba]

I like your idea.
Thanks a lot.

Check out that:

unsigned long int number = /*...*/;
unsigned int divisors = 0;

for(unsigned long int i=2 ; i < t.size() && i*i <= number ; i++)		
		{
			while(!(number%i))
			{
				number /= i;
				
				t[i]++;
			}
			
			if(t[i]) divisors *= (t[i]+1);
		}

If there is something i can do to speed it up...

[sequba]

Yea!
Finally it works and it's fast enough.

If you want to see it...:

unsigned int divisors(unsigned long int n)
{
	unsigned short int primes[10000];
	for(unsigned int i=0 ; i < 10000 && i <= n ; i++) primes[i]=0;
	
	unsigned short int how_many=1;
	for(unsigned long int i=2 ; i < 10000 && i <= n ; i++)		
	{
		while(!(n%i))
		{
			n /= i;
			
			primes[i]++;
		}
		
		if(primes[i]) how_many *= (primes[i]+1);
	}
	
	return how_many;
}

[ne555]

The idea was that primes is an array that have prime numbers (that you calculate before, maybe dynamical)
So your steps will be greater, because you don't test against every number.


What if your input is a prime number greater than 1000? You will return 1.

[sequba]

You're right, but this is enough for me at the moment. Maybe I'll try to improve it later.

Thank you very much for your help.