Counting number of divisors

general
,
1

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;

}
3

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

4

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

5

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:

1 Like
6

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

Submission #92523992 - Codeforces here is the code for further reference