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) ...