Search⌘ K
AI Features
Home
Courses
Competitive Programming in C++: The Keys to Success

Solved Problem - Factorization

Explore how to count the number of factors of a given number efficiently by applying mathematical insights that reduce complexity from linear to square root time. Understand factor pairs and optimization strategies that enable faster computation for large values, preparing you for more advanced number theory problems.

We'll cover the following...

Problem statement

Given a number N>1N > 1, count the number of factors of the number N.

Input format

A single line of input contains the number 1≤N≤10121 \leq N \leq 10^{12}.

Output format

Print a single integer equal to the number of factors of NN.

Sample

Input

36

Output

9

Explanation

Factors of 36:1,2,3,4,6,9,12,18,3636 : 1, 2, 3, 4, 6, 9, 12, 18, 36

Count: 99

Brute force

The brute force solution would be to loop over all the numbers from 1 to N and check if it is a factor. If it is, you would then print it.

We can use the modulus operator to check if it’s a factor or not.

Here is the code:

C++
#include <iostream>
#include <fstream>
#define lli long long int
using namespace std;
int print_factors_count(lli N) {
  int cnt = 0;
  for (int i = 1; i <= N; i ++)
    if (N % i == 0)
      cnt ++;
  return cnt;
}
int main() {
  ifstream cin("input.txt");
  int N;
  cin >> N;
  cout << print_factors_count(N);
  
  return 0;
}

Since there is only one loop that runs N times, the runtime complexity is simply O(N)O(N).

This is good enough for NN up to 10610^6 or even 10810^8, but it will not work with the given constraints. Typically, you have 1-3 seconds for the code to execute and print the results.

Let’s see how we can optimize it further.

Optimization

Let’s take a number, n, and one of its factors, a. Then there must be another factor, b, such that

a∗b=na * b = n

or b=nab = \frac{n}{a}

Also, let’s assume a<=na<=\sqrt{n}

1a>=1n\frac{1}{a} >= \frac{1}{\sqrt{n}}

na>=nn\frac{n}{a} >= \frac{n}{\sqrt{n}}

b>=nb >= \sqrt{n}

Which means if we find two factors, a and b of n such that ab=n, one is always less than or equal to n\sqrt{n} and the other one is greater than or equal to n\sqrt{n}.

Factors always come in pairs, except when the number is a perfect square. In which case both factors are equal.

Based on this observation, we only need to iterate up to N\sqrt{N} times. The complexity is reduced to O(N)O(\sqrt{N}).

Below is the optimized code for the above problem.

C++
#include <iostream>
#include <fstream>
#define lli long long int
using namespace std;
int print_factors_count(lli N) {
  int cnt = 0;
  for (int i = 1; i * i <= N; i ++)
    if (N % i == 0) {
      cnt ++;
      if (i != N/i)
        cnt ++;
    }
  return cnt;
}
int main() {
  ifstream cin("input.txt");
  
  int N;
  cin >> N;
  cout << print_factors_count(N);
  return 0;
}

In the next lesson, we’ll see how we can use the same observation to speed up the primality test. The primality test determines whether the input is prime or not.