Competitive Programming in C++: The Keys to Success/

...

/

Solved Problem - Factorization

Solved Problem - Factorization

In the lesson, we look at an efficient way to factor a number.

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:

Press + to interact
main.cpp
input.txt
#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) ...