Efficiently getting all divisors of a given number

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.

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';
}

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.

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.