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 <= num; ++i){
    if (num % i == 0)
        cout << i << 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:

1. Find all prime factors of the given number through this solution.
2. Get all possible combinations of those prime factors.

However, it doesn't seem to be a good one.

Answer 1

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 in the example above:

00
01
10
11
20
21

gives you the 6 factors.

Answer 2

The best approach is to find the prime factorization of the number, then use that to construct the answer.

What is the fastest integer factorization algorithm? offers a set of strategies if you want a state of the art solution. But I'll be lazy, and do it in Python with primefac doing the heavy lifting. Even though this is in Python, it is much faster than the others. Try it with a 20 digit number of your choice if you don't believe me.

from primefac import primefac
import heapq

def all_factors (n):
    prime_count = {}
    for p in primefac(n):
        prime_count[p] = prime_count.get(p, 0) + 1
    prime_freq = list(prime_count.items())

    upcoming = [(1, 0)]
    while 0 < len(upcoming):
        factor, next_i = heapq.heappop(upcoming)
        yield factor
        for i in range(next_i, len(prime_freq)):
            p, p_count = prime_freq[i]
            p_pow = p
            for _ in range(p_count):
                heapq.heappush(upcoming, (factor * p_pow, i+1))
                p_pow *= p

for f in all_factors(845234800983120319000):
    print(f)

Answer 3

seems the best way is to factor an integer and sort its factors, then use recursion to print divisors in order.

this is from sympy's soruce code:

def _divisors(n, proper=False):
    """Helper function for divisors which generates the divisors.

    Parameters
    ==========

    n : int
        a nonnegative integer
    proper: bool
        If `True`, returns the generator that outputs only the proper divisor (i.e., excluding n).

    """
    if n <= 1:
        if not proper and n:
            yield 1
        return

    factordict = factorint(n)
    ps = sorted(factordict.keys())

    def rec_gen(n=0):
        if n == len(ps):
            yield 1
        else:
            pows = [1]
            for _ in range(factordict[ps[n]]):
                pows.append(pows[-1] * ps[n])
            yield from (p * q for q in rec_gen(n + 1) for p in pows)

    if proper:
        yield from (p for p in rec_gen() if p != n)
    else:
        yield from rec_gen()

Answer 4

If the prime factors are known those 3 functions can be used to get the divisors:

    public static <T> Set<List<T>> generatePowerSet(List<T> list) {
        Set<List<T>> powerSet = new HashSet<>();
        generatePowerSet(list, 0, new ArrayList<>(), powerSet);
        return powerSet;
    }

    private static <T> void generatePowerSet(List<T> list, int index, List<T> current, Set<List<T>> powerSet) {
        if (index == list.size()) {
            powerSet.add(new ArrayList<>(current));
            return;
        }
        // Exclude the current element
        generatePowerSet(list, index + 1, current, powerSet);
        // Include the current element
        current.add(list.get(index));
        generatePowerSet(list, index + 1, current, powerSet);
        current.remove(current.size() - 1);
        // Skip duplicate elements
        while (index + 1 < list.size() && list.get(index) == list.get(index + 1)) {
            index++;
        }
        generatePowerSet(list, index + 1, current, powerSet);
    }
    public SortedListSet<Long> getDivisors(ArrayList<Long> primeFactors){
        SortedListSet<Long> divisors = new SortedListSet<>();
        Set<List<Long>> powerSet = generatePowerSet(primeFactors);
        for (List<Long> innerList:powerSet){
            long divisor = 1;
            for (long innerListEntry:innerList){
                divisor *= innerListEntry;
            }
            divisors.add(divisor);
        }
        return divisors;
    }

Answer 5

java 8 recursive (works on HackerRank). This method includes option to sum and return the factors as an integer.

    static class Calculator implements AdvancedArithmetic {
        public int divisorSum(int n) {
            if (n == 1)
                return 1;

            Set<Integer> set = new HashSet<>();
            return divisorSum( n, set, 1);
        }

        private int divisorSum(int n, Set<Integer> sum, int start){

            if ( start > n/2 )
                return 0;

            if (n%start == 0)
                sum.add(start);

            start++;

            divisorSum(n, sum, start);

            int total = 0;
            for(int number: sum)
                total+=number;
            return total +n;
        }
    }

Answer 6

We can use modified sieve for getting all the factors for all numbers in range [1, N-1].

for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
        ans[j].push_back(i);
    }
}

The time complexity is O(N * log(N)) as the sum of harmonic series 1 + 1/2 + 1/3 + ... + 1/N can be approximated to log(N).

More info about time complexity : https://math.stackexchange.com/a/3367064

P.S : Usually in programming problems, the task will include several queries where each query represents a different number and hence precalculating the divisors for all numbers in a range at once would be beneficial as the lookup takes O(1) time in that case.

Answer 7

If you want all divisors to be printed in sorted order

int i;
for(i=1;i*i<n;i++){             /*print all the divisors from 1(inclusive) to
    if(n%i==0){                   √n (exclusive) */   
        cout<<i<<" ";
    }
}
for( ;i>=1;i--){                /*print all the divisors from √n(inclusive) to
  if(n%i==0){                     n (inclusive)*/   
      cout<<(n/i)<<" ";
  }
}

If divisors can be printed in any order

for(int j=1;j*j<=n;j++){
    if(n%j==0){
        cout<<j<<" ";
        if(j!=(n/j))
           cout<<(n/j)<<" ";
    }
}

Both approaches have complexity O(√n)

Answer 8

#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define fo(i,k,n) for(int i=k;i<=n;++i)
#define endl '\n'
ll etf[1000001];
ll spf[1000001];
void sieve(){
    ll i,j;
    for(i=0;i<=1000000;i++) {etf[i]=i;spf[i]=i;}
    for(i=2;i<=1000000;i++){
        if(etf[i]==i){
            for(j=i;j<=1000000;j+=i){
                etf[j]/=i;
                etf[j]*=(i-1);
                if(spf[j]==j)spf[j]=i;
            }
        }
    }
}
void primefacto(ll n,vector<pair<ll,ll>>& vec){
    ll lastprime = 1,k=0;
    while(n>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<pair<ll,ll>>& vec,ll idx,vector<ll>& divs,ll num){
    if(idx==vec.size()){
        divs.push_back(num);
        return;
    }
    for(ll i=0;i<=vec[idx].second;i++){
        divisors(vec,idx+1,divs,num*pow(vec[idx].first,i));
    }
}
void solve(){
    ll n;
    cin>>n;
    vector<pair<ll,ll>> vec;
    primefacto(n,vec);
    vector<ll> divs;
    divisors(vec,0,divs,1);
    for(auto it=divs.begin();it!=divs.end();it++){
        cout<<*it<<endl;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    sieve();
    ll t;cin>>t;
    while(t--) solve();
    return 0;
}

Answer 9

//DIVISORS IN TIME COMPLEXITY sqrt(n)

#include<bits/stdc++.h>
using namespace std;

#define ll long long

int main()
{
    ll int n;
    cin >> n;

    for(ll i = 2;  i <= sqrt(n); i++)
    {
        if (n%i==0)
        {
            if (n/i!=i)
                cout << i << endl << n/i<< endl;
            else
                cout << i << endl;
        }
    }
}

Answer 10

for( int i = 1; i * i <= 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
*/

Answer 11

for (int i = 1; i*i <= num; ++i)
{
    if (num % i == 0)
    cout << i << endl;
    if (num/i!=i)
    cout << num/i << endl;
}

Answer 12

Here is the Java Implementation of this approach:

public static int countAllFactors(int num)
{
    TreeSet<Integer> tree_set = new TreeSet<Integer>();
    for (int i = 1; i * i <= 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();
}

Answer 13

int result_num;
bool flag;

cout << "Number          Divisors\n";

for (int number = 1; number <= 35; number++)
{
    flag = false;
    cout << setw(3) << number << setw(14);

    for (int i = 1; i <= number; i++) 
    {
        result_num = number % i;

        if (result_num == 0 && flag == true)
        {
            cout << "," << i;
        }

        if (result_num == 0 && flag == false)
        {
            cout << i;
        }

        flag = true;
    }

    cout << endl;   
}
cout << "Press enter to continue.....";
cin.ignore();
return 0;
}

Answer 14

//Try this,it can find divisors of verrrrrrrrrry big numbers (pretty efficiently :-))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<conio.h>

using namespace std;

vector<double> D;

void divs(double N);
double mod(double &n1, double &n2);
void push(double N);
void show();

int main()
{
    double N; 
    cout << "\n Enter number: "; cin >> N;

    divs(N); // find and push divisors to D

    cout << "\n Divisors of "<<N<<": "; 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 <= sqrt(N); ++i)
    {
        if (!mod(N, i)) { push(i); if(i*i!=N) push(N / i); }
    }
}

double mod(double &n1, double &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 <= e)
    {   
        if (N==D[m-1]) { return; }
        else if (N > 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 < D.size(); ++i) cout << D[i] << " ";
}

Answer 15

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 < square_root; i++) { 
    if (num % i == 0&&i*i!=num)
        cout << i << num/i << endl;
    if (num % i == 0&&i*i==num)
        cout << i << '\n';
}

Answer 16

Here's my code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int, int>

#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>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

// http://zobayer.blogspot.com/2009/09/segmented-sieve.html
void sieve()
{
    unsigned i, j, k;
    for (i = 3; i<LMT; i += 2)
        if (!chkC(base, i))
            for (j = i*i, k = i << 1; j<MAX; j += k)
                setC(base, j);
    primes[0] = 2;
    for (i = 3, j = 1; i<MAX; i += 2)
        if (!chkC(base, i))
            primes[j++] = i;
}


//http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
vector <pii> factors;
void primeFactors(int num)
{
    int expo = 0;   
    for (int i = 0; primes[i] <= sqrt(num); i++)
    {
        expo = 0;
        int prime = primes[i];
        while (num % prime == 0){
            expo++;
            num = num / prime;
        }
        if (expo>0)
            factors.push_back(make_pair(prime, expo));
    }

    if ( num >= 2)
        factors.push_back(make_pair(num, 1));

}

vector <int> divisors;
void setDivisors(int n, int i) {
    int j, x, k;
    for (j = i; j<factors.size(); j++) {
        x = factors[j].first * n;
        for (k = 0; k<factors[j].second; k++) {
            divisors.push_back(x);
            setDivisors(x, j + 1);
            x *= factors[j].first;
        }
    }
}

int main() {

    sieve();
    int n, x, i; 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        primeFactors(x);
        setDivisors(1, 0);
        divisors.push_back(1);
        sort(divisors.begin(), divisors.end());
        cout << divisors.size() << "\n";
        for (int j = 0; j < divisors.size(); j++) {
            cout << divisors[j] << " "; 
        }
        cout << "\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.

Answer 17

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.

Answer 18

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.