Number of Factors (Codechef Level:-Medium)

Question

Alice has learnt factorization recently. Bob doesn't think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of N numbers. Alice is frightened of big numbers and hence is asking you for help. Your task is simple. Given N numbers, you need to tell the number of distinct factors of the product of these N numbers.

Input First line of input contains a single integer T, the number of test cases.

Each test starts with a line containing a single integer N. The next line consists of N space separated integers (Ai).

Output For each test case, output on a separate line the total number of factors of the product of given numbers.

Constraints 1 ≤ T ≤ 100, 1 ≤ N ≤ 10, 2 ≤ Ai ≤ 1000000

My Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    long long int p = 1, a, c = 0;
    while (n--) {
      cin >> a;
      p *= a;
    }
    for (int i = 1; i <= p; i++) {
      if (p % i == 0)
        c++;
    }
    cout << c << endl;
  }
  return 0;
}

When compiling my program in Codechef, only small numbers are being executed.The larger numbers cannot be compiled. So in Codechef the result is showing "Time Limit Exceeded(TLE)".

Unrelated to your problem, but please take some time to read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Some programmer dude, Mar 17 '20 at 17:32
Also please stop using online judge- and competition-sites as a learning resource, because they're not. Please pick up [a couple of good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) or take a class or two instead. — Some programmer dude, Mar 17 '20 at 17:34
Look at the worst case scenario. The product of ten 1000000's (1000000^10) is 10^60. 10^60 iterations of one nanosecond each would take over 3*10^43 years. Even when limited to signed 64 bits, iterating over all the positive numbers one nanosecond at a time would take almost 300 years. You need a much cleverer method than a brute-force search, and Alice was right to be frightened of big numbers. — molbdnilo, Mar 17 '20 at 17:44
Instead of finding the product of all Ai, and then factoring, could you find prime factors of each input, and then use the individual prime factors to calculate all unique factors of the product? — LLSv2.0, Mar 17 '20 at 18:11
Does this answer your question? [Factor a large number efficiently with gmp](https://stackoverflow.com/questions/4301434/factor-a-large-number-efficiently-with-gmp) — LLSv2.0, Mar 17 '20 at 18:16

score 0 · Answer 1 · answered Mar 17 '20 at 18:13

Your approach to the problem does not take advantage of an important aspect of it, that is, the number is already expressed as a product of some integers. Therefore, if you can find the prime factorization of each of those N numbers separately (can be done efficiently in O(logn), using the sieve algorithm), then it is as simple as counting the number of unique factors among them.

Number of Factors (Codechef Level:-Medium)

1 Answers1