ACM (TJU) : 2076


// http://acm.tju.edu.cn/toj/showp2076.html

#include <stdio.h>

int main ()
{
    int dataset;
    scanf ("%d", &dataset);

    while ( dataset-- ) {
        int n;
        scanf ("%d", &n);

        bool a [105];

        for ( int i = 1; i <= n; i++ )
            a [i] = true;

        for ( int i = 2; i <= n; i++ ) {
            for ( int j = i; j <= n; j += i ) {
                if ( a [j] )
                    a [j] = false;
                else
                    a [j] = true;
            }
        }

        int count = 0;

        for ( int i = 1; i <= n; i++ ) {
            if ( a [i] )
                count++;
        }

        printf ("%d\n", count);

    }

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s