C/C++ Is there an efficient way to find divisors of large numbers using C++?

[smslca]

As I saw in wolfram website and in pari , if given divisors(x) , it will give all the divisors of x in a row.
ex: divisors (34567) = { 1, 13, 2659, 34567 }
So I we know some x = 2^5 * 5^15 * 21^5 * 119 , Here we even know the prime factors
Then,
Is there any program in c language (or) any other easily understood computer programing language (so that I could convert into a c program using the same logic , since I know only c language programing) , (or) any easy algorithm to form
divisors at very fast speeds (because I require to form divisors for very large numbers) .
If anyone have the code please give me , or any step wise explained algorithm is also sufficient.

Here I can formulate an algorithm by observing the factors of the number (i.e using the arrangement of factors in ascending or descending order), but I think ,this method is too slow to form the divisors for very very large numbers having a lot and lot of divisors in it.

 

[JackCrow]

Heres the code :D

Heres the code, enjoy :D

#include <stdio.h>
#include <conio.h>

int main()
{
long int n, d=2;
printf("Enter the number:");
scanf("%d", &n); 
printf("\n\n The divisor(s) : { 1 ");
while(d<= n/2)
 {
  if(n%d==0) printf("%d ", d);
  d++;
 }
printf("%d } \n", n);
getch();
return(0);
}

 

[chiro]

As I saw in wolfram website and in pari , if given divisors(x) , it will give all the divisors of x in a row.
ex: divisors (34567) = { 1, 13, 2659, 34567 }
So I we know some x = 2^5 * 5^15 * 21^5 * 119 , Here we even know the prime factors
Then,
Is there any program in c language (or) any other easily understood computer programing language (so that I could convert into a c program using the same logic , since I know only c language programing) , (or) any easy algorithm to form
divisors at very fast speeds (because I require to form divisors for very large numbers) .
If anyone have the code please give me , or any step wise explained algorithm is also sufficient.

Here I can formulate an algorithm by observing the factors of the number (i.e using the arrangement of factors in ascending or descending order), but I think ,this method is too slow to form the divisors for very very large numbers having a lot and lot of divisors in it.

The code posted above should work but it is by no means optimal.

In fact the current thinking in finding prime factors for a large number is that there is no decent algorithm that will factorize large numbers in a decent time.

The RSA algorithm uses this property to enforce the strength of its public key cryptography system.

If you end up finding a fast method that decomposes an arbitrary large number into primes, then you will be famous and probably considered dangerous as well ;)

 

[smslca]

Its very very useful . thanks for giving the code

 

[TylerH]

JackCrow's solution, in theory, could fail for numbers < 4, and will be atrociously inefficient for large numbers. It's better to replace "while(d<= n/2)" with "d <= (long int)sqrt((double)d)". Consider the case d=100. It is obvious that the two largest factors for all d is sqrt(d), thus this loop need only execute 10 times, at most. With d/2 as your exit condition, you're checking 11-50, which is completely unnecessary. We can do some math and find just how ineffiecient if is, given a general d. The sqrt d is what is necessary and all more than that in not, so we'll d/2 - sqrt(d). Think of very large numbers, such as 2^16, that would be 2^15 - 2^8 extraneous iterations.

Another way to consider would be recursion. Although sometimes a little more inefficient than iteration, recursion is almost always more fun. A way you could do this with recursion would be to find the lowest factor >1 in the argument, then call the function recursively with the previous argument divided by the factor. Like so:

#include <stdio.h>
#include <math.h>

void factor(unsigned long long n);

int main(int argc, char **argv)
{
     factor(4896542);
     return 0;
}

void factor(unsigned long long n)
{
     for(unsigned long i = 2;i <= (unsigned int)sqrt((double)n);i++)
          if(n % i == 0)
          {
               printf("%u ", i)
               factor(n / i);
               break;
          }
}

The only problem is that it doesn't print 1, if you want it to, add it in main.

 

[smslca]

JackCrow's solution, in theory, could fail for numbers < 4, and will be atrociously inefficient for large numbers. It's better to replace "while(d<= n/2)" with "d <= (long int)sqrt((double)d)". Consider the case d=100. It is obvious that the two largest factors for all d is sqrt(d), thus this loop need only execute 10 times, at most. With d/2 as your exit condition, you're checking 11-50, which is completely unnecessary. We can do some math and find just how ineffiecient if is, given a general d. The sqrt d is what is necessary and all more than that in not, so we'll d/2 - sqrt(d). Think of very large numbers, such as 2^16, that would be 2^15 - 2^8 extraneous iterations.

Thanks for modifying the code.
I just wanted to know how to store the divisors.

I am working on factorization of numbers. So I got a problem where I have to form the divisors for an another number (another number = given number - some number), for which I can get the factors easily.

ex: say I got factors of an another number as 2^32 * 3^12* 5^10 * 383 * 1151
Here I knew I will get 33*13*11*2*2 = 11876 divisors

But the problem is , not the number of divisors , it is what are the divisors and how can I store them.

Sincerely , I am not expecting the above given codes. But on watching them I got some Idea about the formation of divisors.

 

[TylerH]

This is where using C++ is nice, with it's vectors and such. There is no way easier than using an array, and having to dynamically resize it for each new factor.