Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hasinur The Great

By tanu_RUET · Limits 2s, 512 MB

Recently Hasinur The Great is dating a girl. Getting inspired from Hasinur's coding skill , she decided to be a programmer too. But, as she is not so experienced she can't write program so efficiently . Recently she tried an problem that Hasinur gave her to solve but got TLE (Time Limit Exceeded ) . Now , let me introduce you with the dark side of Hasinur The Great. He is a mad programmer. He is very nice and gentleman. But if his girlfriend can't solve problem that he gives her, he becomes very angry. Now as you are a well wisher of Hasinur and his family , please help his girlfriend. She wrote the code given below:

#include<bits/stdc++.h>
using namespace std;

int IsPrime(int a)
{
    int x;
    for(x = 2; x < a; x++){
        if(a % x == 0)
            return 0;
    }
    return 1;
}

int DistinctPrimeCount(int n)
{
    int i, j = 0;
    for(i = 2; i <= n; i++){
        if(n % i == 0)
            j += IsPrime(i);
    }
    return j;
}

int main()
{
    int N, M, i, j, k;
    scanf("%d", &N);

    for(i = 0; i < N; i++){
        scanf("%d", &M);
        printf("%d\n",DistinctPrimeCount(M));
    }    
}

Nothing hard , you have to make this code efficient so that it gets accepted for N ≤ 5000000 and M ≤ 5000000.

Input

In first line there will be an integer N. And then there will be N lines, each containing an integer M.

1 ≤ N ≤ 5000000
0 ≤ M ≤ 5000000

Output

Print an integer for each input M, the output of the given code.

Sample

InputOutput
2
1
2
0
1

Discussion

Statistics


46% Solution Ratio

prodip_bsmrstuEarliest, Nov '18

rifatrraazzFastest, 0.5s

rifatrraazzLightest, 16 MB

raselrokyShortest, 252B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.