All Factors of a Natural Number in C++

In this tutorial, we will be looking at all the methods to find all factors of a natural number n.

Query

Given a natural number n, print all distinct factors of n.

C++ Implementation: All Factors of a Natural Number

To handle the above-mentioned query we will solve it from a very naive to a very sophisticated process. So please scroll the tutorial till the end.

Let’s first look at the Naive Solution for that query:

In our Naive Solution, we would iterate from all natural numbers ranging from 1 to n, check whether that number divides n, and add it to our solution. Let’s have a look at the C++ implementation for the same:

#include"bits/stdc++.h"
using namespace std;
#define int long long // To prevent integer overflow

// Function which returns a vector that contains all the factors of a natural number n
vector<int>Naive_Factors_Find(int n){
  vector<int>V;
  for(int i=1; i<=n; i++)
  {
    if(n%i==0) // If the remainder upon division is 0, it means that its one a factor of n
    V.push_back(i);
  }
  return V;
}

signed main(){
  int n = 144;
  vector<int> V = Naive_Factors_Find(n);
  cout<<"All distinct factors of the given natural number "<<n<<" are: "<<endl;
  for(auto it: V)
  cout<<it<<" ";
}

Output

All distinct factors of the given natural number 144 are:
1 2 3 4 6 8 9 12 16 18 24 36 48 72 144

Time Complexity: O(n)

Space Complexity: O(1)

This Naive Solution is very slow and when n gets sufficiently larger it will take a huge amount to execute. It is also not preferred to use this approach when you are solving Competitive Programming Problems.

Now, let’s have a look at another approach and improve our Time Complexity of implementation, yet this is not the fastest approach:

If we observe the results we obtained while finding all factors of a natural number n, we can see that the pair of factors form a divisor and quotient for the number n. Let’s consider an example of n = 144, we can find those pairs formed as: (1, 144), (2, 72), (3, 48), (4, 36), (8, 24), (9, 16) and (12, 12).

If we observe it, we can notice that instead of iterating from 1 to n, if we did iterate from 1 to sqrt(n), we could have found all distinct factors.

Using this idea, we can think of another implementation to speed up our program significantly:

#include"bits/stdc++.h"
using namespace std;
#define int long long // To prevent integer overflow

// Function which returns a set that contains all the factors of a natural number n
set <int> Sqrt_Method_Factors_Find(int n){
  set<int>V;
  for(int i=1; i<=sqrtl(n); i++)
  {
    if(n%i==0) // If the remainder upon division is 0, it means that its one a factor of n
    {
      V.insert(i);
      if(n/i != i) // Ensuring we don't put the same number twice in our vector
      V.insert(n/i);
    }
  }
  return V;
}

signed main(){
  int n = 144;
  set<int> V = Sqrt_Method_Factors_Find (n);
  cout<<"All distinct factors of the given natural number "<<n<<" are: "<<endl;
  for(auto it: V)
  cout<<it<<" ";
}

Output

All distinct factors of the given natural number 144 are:
1 2 3 4 6 8 9 12 16 18 24 36 48 72 144

Time Complexity: O(sqrt (n))

Space Complexity: O(1)

Now we will look at the fastest approach to tackle this problem, which is using the Mathematical Concept of Pollard Rho and Miller Rabin Algorithm to get the prime factorization of number n, and using DFS to find all distinct factors from the prime factorization obtained previously. The implementation of the same is provided below:

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


// Function which returns a set that contains all the factors of a natural number n
namespace PollardRho {
  long long power(long long x, long long p, long long mod){ // Returns (x^p)%mod
    long long answer = 1;
    while(p)
    {
      if(p&1)
      answer = (__int128)answer*x%mod;
      x = (__int128) x * x % mod;
      p>>=1;
    }
    return answer;
  }

  long long MillerRabin(long long x, long long b) {
    // it checks whether x is a Prime number or not
    // b determines how many times the MillerRabin is called
    // The greater the value b, the more is the prediction accuracy
    long long k = x-1;
    while(k) {
      long long cur = power(b,k,x);
      if(cur != 1 && cur != x-1)
      return false;
      if((k&1)==1 || cur == x-1)
      return true;
      k>>=1;
    }
    return true;
  }

  bool Prime(long long x) { // function to return whether a number is Prime or not
    if(x==46856248255981ll || x < 2)
    return false;
    if(x==2 || x==3 || x==7 || x==61 || x==24251)
    return true;
    return MillerRabin(x, 2) && MillerRabin(x, 61);
  }

  long long PR (long long x) { // Pollard Rho implementation
    long long y=1ll*rand()*rand()%x+1, v0=1ll*rand()*rand()%(x-1)+1, v=v0, d, s=1;
    int t=0, k=1;
    while(1){
      v=((__int128)v*v+y)%x;
      s=(__int128)s*(max(v,v0)-min(v,v0))%x;
      if(v==v0 || !s)
      return x;
      if(++t==k)
      {
        if((d=__gcd(s,x))^1)
        return d;
        v0=v;
        k<<=1;
      }
    }
 }

 long long NonTrivialFact(long long x) {
   if(Prime(x))
   return -1;
   long long answer = 1;
   while (answer == 1 || answer == x)
   answer = PR(x);
   return answer;
 }

 void dfs (long long x, vector<long long> &answer) {
   if(Prime(x)) {
     answer.push_back(x);
     return;
   }
   long long t = NonTrivialFact(x);
   dfs(t, answer);
   dfs(x/t, answer);
 }

 vector<long long> PrimeFacList (long long x) { // Returns prime factor list of x
   if(x==1)
   return {};
   vector<long long>answer;
   dfs(x, answer);
   return answer;
 }

};

#define int long long // To prevent integer overflow

namespace fact {
  const int n=1000000;
  bitset<n+2> isPrime;
  int OneFac[n+2];
  vector<int> Prime;

  void Fac_dfs(int x, int y, vector<int> &ans, vector<pair<int,int>>& FacList) {
    if(x==(int)(FacList.size())) {
      ans.push_back(y);
      return;
    }
    int k = 1;
    for(int i=0; i<=FacList[x].second; i++) {
      Fac_dfs(x+1, y*k, ans, FacList);
      k*=FacList[x].first;
    }
  }

  vector<pair<int,int>>GetPrimeFac(int a) {
    if(a==1)
    return {};
    vector<pair<int,int>> answer;
    if(isPrime [a])
    return vector<pair<int,int>> {pair<int,int>{a,1}};
    answer.push_back({OneFac[a], 1});
    a/=OneFac[a];
    while(!isPrime[a]) {
      if(OneFac[a] == answer.back().first)
      answer.back().second++;
      else
      answer.push_back({OneFac[a], 1});
      a/=OneFac[a];
    }
    if(a == answer.back().first)
    answer.back().second++;
    else
    answer.push_back({a, 1});
    return answer;
  }

  vector<int>GetFacList (int a) {
    vector<int> ans;
    vector<pair<int,int>>FacList = GetPrimeFac(a);
    Fac_dfs(0, 1, ans, FacList);
    return ans;
  }

  void init() {
    for(int i=0; i<n; i++)
    isPrime[i]=1;
    for(int i=2; i<=n; i++)
    {
      if(isPrime[i])
      Prime.push_back(i);
      for(int j: Prime) {
        if(i*j > n)
        break;
        isPrime[i*j]=0;
        OneFac[i*j]=j;
        if(i%j == 0)
        break;
      }
    }
  }

};

vector<pair<int, int>> vi2vp (vector<int>q) {
  vector<pair<int,int>> p;
  sort(q.begin(), q.end());
  for(int i: q) {
    if(p.empty() || p.end()[-1].first != i)
    p.push_back({i, 1});
    else
    p.end()[-1].second++;
  }
  return p;
}

vector<int>GetFacList(vector<pair<int,int>>FacList) {
  vector<int> ans;
  fact::Fac_dfs(0,1,ans,FacList);
  return ans;
}

vector<int>GetFacList(int x) {
  return GetFacList(vi2vp(PollardRho::PrimeFacList(x)));
}

signed main(){
  int n = 19260817ll*2147483647ll; // A very long number
  cout<<"All distinct factors of given natural number "<<n<<" are: "<<endl;
  vector<int> ans = GetFacList(n);
  sort(ans.begin(), ans.end());
  for(auto it: ans)
  cout<<it<<" ";
  cout<<endl;
}

Output

All distinct factors of given natural number 41362289535359599 are: 
1 19260817 2147483647 41362289535359599

Time Complexity: O(max(n¼ * log (n), d(n)) . Here d(n)denotes the distinct factors of n.

Space Complexity: O(1)

As you can it works even for very large numbers in the fastest way possible. It is advised to use this implementation for any Competitive Programming Problems.