 # Counting number of divisors

I was solving this problem. But something wrong in the code that I am getting TLE. And I had a limitation of 10^12.
Is my code of assert right?

``````#include <iostream>
#include <assert.h>
using namespace std;

int count_divisor(long long int number){
long long int count = 0;
for(long long int i = 1; i <= number; i++){
if(number%i == 0){
count++;
}
}
return count;
}

int main(){
long long int test_case, i = 1;
long long int numbers;

cin >> test_case;
//assert(test_case >= 1 && test_case <= 100000);
while(i <= test_case){
cin >> numbers;
//assert(numbers >= 1 && numbers <= 1000000000000);
if(count_divisor(numbers) == 3){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
i++;
}
return 0;

}
``````

Your function runs at O(N), which may not work for very long numbers…

Consider 10^8 steps ~ 1 second

So 10^12 ~ 10000 seconds

We need not count the no.of divisors because 1 and n are already divisors .say i is a divisor then other divisor is n/i whuch results in total of 4 divisors so i==n/i and i should be a prime number so the sqrt of given number should be prime for it to have 3 divisors

The thing to note is that if the given number is a square number and the square root of that is prime,then only its a T-prime number.

You can see my solution:
https://codeforces.com/contest/230/submission/75032663

1 Like

You can sieve and calculate all the prime numbers up to 10^6.Then run a loop through the list of primes and check whether the number is a square of any prime number.
I think this with few optimizations should be enough to pass the time limit

https://codeforces.com/contest/230/submission/92523992 here is the code for further reference