Maximum k-length sequence of divisors of a given integer in C++

By Vikram singhal

It’s a number theory problem and can also be categorized under constructive algorithm problems

pre-requisites: Prime-factorization

PROBLEM STATEMENT:

Given an integer N.Our task is to find a sequence of length K i.e., { a_1,a_2,a_3,………,a_{k } in C++.}

And the following conditions must satisfy for the K- length sequence;

each a_i > 1,
K is the maximum possible i.e., length of the sequence is maximum possible,
for each, i=1 to k-1, a_i+1 is divisible by a_i,
all elements of this k-length sequence multiply to N (given no).

Try this problem for yourself first and then go for a given solution.

Solution :

This solution to this problem can be thought of easily if we try to approach this problem through prime factorization. We know that all the integers can be decomposed to their prime-factors. And it is also a fact that no unique prime-factor of an integer will divide another prime-factor of that integer.

And all the prime-factors are also strictly greater than 1.so, we can emphasize these points to solve this problem.

Another important point to consider in this problem is about the maximum length of K. To get the maximum length of k, we’ll keep a track of the repetition of every prime-factor of N and store the value of prime-factor and its occurrence during prime-factorization of N.

Another point to note in the problem statement is that in our maximum k- length sequence of factors of N, all the a_i+1 should be divisible by a_ifor each, i=1 to k-1. We can take care of this point by first inserting the Prime- factor whose frequency is maximum during prime-factorization one less time than its frequency and the last element in the sequence will be the product of prime-factor which has a maximum frequency and the quotient when N is divided by (prime-factor with maximum frequency * the count of previous elements into the sequence).

Input format:

The first input will be the no of test cases,
Then will read t lines of each containing N(>=2), the given no.

Output format:

for every t-test cases, we will output 2 lines

first-line will contain the k (the maximum possible size of sequence)
The second will contain the required sequence itself in which the element will be space-separated.

It will be easy to see the solution to this problem in the code itself. Let’s code it!

C++ code of solution to this problem

typedef long long int ll; // macro to define the long integer type
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t; // taking input the no. of test cases.
    while(t--)
    {
        ll n;cin>>n;   // using ll for long long int to avoid integer overflow.
        ll n_copy=n;   // to create a copy variable of n to use it later.
        ll nmax_divisor=0; // to keep track of frequency of every prime factor.
        ll max_divisor; // to store the value of prime factor with maximum frequency.
// below for loop is basically prime-factorization of n in o(sqrt(n)) time - complexity.
        for(ll i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                ll tpdc=0;
                while(n%i==0)
                {
                    n/=i;
                    tpdc++;
                }
                if(tpdc>nmax_divisor) // to keep track of prime- factor with maximum frequency.
                {
                  nmax_divisor=tpdc;
                  max_divisor=i;
                }
            }
        }
        if(nmax_divisor==0) // to handle the case if n is a prime no itself, so it will have no other prime-factor than itself.
        {
            cout<<'1'<<"\n"<<n<<"\n";
        }
        else
        {
            cout<<nmax_divisor<<"\n";
            ll md_product=1;
            for(int i=1;i<nmax_divisor;i++)
            {
                cout<<max_divisor<<' ';   // to print the prime-factor with maximum frequency one less than it's original frequency(nmax_divisor-1) times. 
                md_product*=max_divisor;
            }
            cout<<n_copy/md_product<<"\n";  to print the last element of sequence containg all the other prime-factors multiplied by their occurences and prime-factor with maximum occurences (only one time)
        }
    }
    return 0;
}

Sample-input:

Sample-output:

3
2 2 90

1
1791398

33
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

1
4999999937

Time-complexity: O(sqrt(n)), same as that of finding the prime factorization of N.

Space-complexity: O(1), since no extra array has been created to store the maximum k- length sequence.

If you think that this article has added any value to your algorithmic knowledge, then please share your valuable feedback in the comment section. Thank you!