Efficiently getting all divisors of a given number

Question

According to this post  we can get all divisors of a number through the following codes   for  int i   1  i  lt   num    i       if  num   i    0          cout  lt  lt  i  lt  lt  endl      For example  the divisors of number 24 are 1 2 3 4 6 8 12 24   After searching some related posts  I did not find any good solutions  Is there any efficient way to accomplish this   My solution    Find all prime factors of the given number through this solution  Get all possible combinations of those prime factors    However  it doesn t seem to be a good one

User · Answer

include lt bits stdc   h gt   using namespace std  typedef long long int ll   define MOD 1000000007  define fo i k n  for int i k i lt  n   i   define endl   n  ll etf 1000001   ll spf 1000001   void sieve        ll i j      for i 0 i lt  1000000 i     etf i  i spf i  i       for i 2 i lt  1000000 i             if etf i   i               for j i j lt  1000000 j  i                   etf j   i                  etf j    i-1                   if spf j   j spf j  i                                  void primefacto ll n vector lt pair lt ll ll gt  gt  amp  vec       ll lastprime   1 k 0      while n gt 1           if lastprime  spf n  vec push back make pair spf n  0            vec vec size  -1  second            lastprime spf n           n  spf n           void divisors vector lt pair lt ll ll gt  gt  amp  vec ll idx vector lt ll gt  amp  divs ll num       if idx  vec size             divs push back num           return            for ll i 0 i lt  vec idx  second i             divisors vec idx 1 divs num pow vec idx  first i            void solve        ll n      cin gt  gt n      vector lt pair lt ll ll gt  gt  vec      primefacto n vec       vector lt ll gt  divs      divisors vec 0 divs 1       for auto it divs begin   it  divs end   it             cout lt  lt  it lt  lt endl          int main        ios base  sync with stdio false       cin tie 0  cout tie 0       sieve        ll t cin gt  gt t      while t--  solve        return 0

User · Answer

Here s my code     include  lt iostream gt   include  lt vector gt   include  lt algorithm gt   include  lt cmath gt   using namespace std    define pii pair lt int  int gt    define MAX 46656  define LMT 216  define LEN 4830  define RNG 100032  unsigned base MAX   64   segment RNG   64   primes LEN     define sq x    x   x    define mset x v  memset x v sizeof x    define chkC x n   x n gt  gt 6  amp  1 lt  lt   n gt  gt 1  amp 31     define setC x n   x n gt  gt 6    1 lt  lt   n gt  gt 1  amp 31        http   zobayer blogspot com 2009 09 segmented-sieve html void sieve         unsigned i  j  k      for  i   3  i lt LMT  i    2          if   chkC base  i               for  j   i i  k   i  lt  lt  1  j lt MAX  j    k                  setC base  j       primes 0    2      for  i   3  j   1  i lt MAX  i    2          if   chkC base  i               primes j      i        http   www geeksforgeeks org print-all-prime-factors-of-a-given-number  vector  lt pii gt  factors  void primeFactors int num        int expo   0         for  int i   0  primes i   lt   sqrt num   i                  expo   0          int prime   primes i           while  num   prime    0               expo                num   num   prime                    if  expo gt 0              factors push back make pair prime  expo               if   num  gt   2          factors push back make pair num  1        vector  lt int gt  divisors  void setDivisors int n  int i        int j  x  k      for  j   i  j lt factors size    j              x   factors j  first   n          for  k   0  k lt factors j  second  k                  divisors push back x               setDivisors x  j   1               x    factors j  first                     int main          sieve        int n  x  i       cin  gt  gt  n      for  int i   0  i  lt  n  i              cin  gt  gt  x          primeFactors x           setDivisors 1  0           divisors push back 1           sort divisors begin    divisors end             cout  lt  lt  divisors size    lt  lt    n           for  int j   0  j  lt  divisors size    j                  cout  lt  lt  divisors j   lt  lt                          cout  lt  lt    n           divisors clear            factors clear              The first part  sieve   is used to find the prime numbers and put them in primes   array  Follow the link to find more about that code  bitwise sieve    The second part primeFactors x  takes an integer  x  as input and finds out its prime factors and corresponding exponent  and puts them in vector factors    For example  primeFactors 12  will populate factors   in this way    factors 0  first 2  factors 0  second 2 factors 1  first 3  factors 1  second 1   as 12   2 2   3 1  The third part setDivisors   recursively calls itself to calculate all the divisors of x  using the vector factors   and puts them in vector divisors     It can calculate divisors of any number which fits in int  Also it is quite fast

User · Answer

for  int i   1  i   i  lt   num  i          upto sqrt is because every divisor after sqrt     is also found when the number is divided by i     EXAMPLE like if number is 90 when it is divided by 5     then you can also see that 90 5   18     where 18 also divides the number     But when number is a perfect square     then num   i    i therefore only i is the factor

User · Answer

There is no efficient way in the sense of algorithmic complexity  an algorithm with polynomial complexity  known in science by now  So iterating until the square root as already suggested is mostly as good as you can be   Mainly because of this  a large part of the currently used cryptography is based on the assumption that it is very time consuming to compute a prime factorization of any given integer

User · Answer

Try this it can find divisors of verrrrrrrrrry big numbers  pretty efficiently  -    include lt iostream gt   include lt cstdio gt   include lt cmath gt   include lt vector gt   include lt conio h gt   using namespace std   vector lt double gt  D   void divs double N   double mod double  amp n1  double  amp n2   void push double N   void show     int main         double N       cout  lt  lt    n Enter number     cin  gt  gt  N       divs N      find and push divisors to D      cout  lt  lt    n Divisors of   lt  lt N lt  lt       show       show contents of D  all divisors of N    getch       used visual studio  if it isn t supported replace it by  getch     return 0      void divs double N        for  double i   1  i  lt   sqrt N     i                if   mod N  i     push i   if i i  N  push N   i              double mod double  amp n1  double  amp n2        return   n1 n2 -floor n1 n2   n2      void push double N        double s   1  e   D size    m   floor  s   e    2       while  s  lt   e                   if  N  D m-1     return            else if  N  gt  D m-1     s   m   1            else   e   m - 1            m   floor  s   e    2             D insert D begin     m  N      void show         for  double i   0  i  lt  D size      i  cout  lt  lt  D i   lt  lt

User · Answer

for  int i   1  i i  lt   num    i        if  num   i    0      cout  lt  lt  i  lt  lt  endl      if  num i  i      cout  lt  lt  num i  lt  lt  endl

User · Answer

You should really check till square root of num as sqrt num    sqrt num    num   Something on these lines   int square root    int  sqrt num    1  for  int i   1  i  lt  square root  i           if  num   i    0 amp  amp i i  num          cout  lt  lt  i  lt  lt  num i  lt  lt  endl      if  num   i    0 amp  amp i i  num          cout  lt  lt  i  lt  lt    n

User · Answer

Here is the Java Implementation of this approach   public static int countAllFactors int num        TreeSet lt Integer gt  tree set   new TreeSet lt Integer gt         for  int i   1  i   i  lt   num  i  1                if  num   i    0                        tree set add i               tree set add num   i                       System out print tree set       return tree set size

User · Answer

Factors are paired  1 and 24  2 and 12  3 and 8  4 and 6    An improvement of your algorithm could be to iterate to the square root of num instead of all the way to num  and then calculate the paired factors using num   i

User · Answer

DIVISORS IN TIME COMPLEXITY sqrt n    include lt bits stdc   h gt  using namespace std    define ll long long  int main         ll int n      cin  gt  gt  n       for ll i   2   i  lt   sqrt n   i                  if  n i  0                        if  n i  i                  cout  lt  lt  i  lt  lt  endl  lt  lt  n i lt  lt  endl              else                 cout  lt  lt  i  lt  lt  endl

User · Answer

int result num  bool flag   cout  lt  lt   Number          Divisors n    for  int number   1  number  lt   35  number          flag   false      cout  lt  lt  setw 3   lt  lt  number  lt  lt  setw 14        for  int i   1  i  lt   number  i                   result num   number   i           if  result num    0  amp  amp  flag    true                        cout  lt  lt       lt  lt  i                     if  result num    0  amp  amp  flag    false                        cout  lt  lt  i                     flag   true             cout  lt  lt  endl       cout  lt  lt   Press enter to continue        cin ignore    return 0

User · Answer

Plenty of good solutions exist for finding all the prime factors of not too large numbers  I just wanted to point out  that once you have them  no computation is required to get all the factors   if N   p 1  a  p  2   b  p  3   c        Then the number of factors is clearly  a 1  b 1  c 1      since every factor can occur zero up to a times   e g  12   2 2 3 1 so it has 3 2   6 factors  1 2 3 4 6 12          I originally thought that you just wanted the number of distinct factors  But the same logic applies  You just iterate over the set of numbers corresponding to the possible combinations of exponents   so int he example above   00 01 10 11 20 21   gives you the 6 factors

[c++] Efficiently getting all divisors of a given number

Examples related to c++

Examples related to algorithm

Examples related to math

Examples related to factorization