POJ1218THE DRUNK JAILER 高速和一般方法两种解法

A certain * contains a long hall of n cells, each right next to each other. Each cell has a *er in it, and each cell is locked. 
One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the 
hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He 
repeats this for n rounds, takes a final drink, and passes out. 
Some number of *ers, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape. 
Given the number of cells, determine how many *ers escape jail.

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n. 

For each line, you must print out the number of *ers that escape when the * has n cells. 

2
5
100

2
10

由于最大才为100，所以就算是用枚举一个个的去改变数值最后也能通过，但是如果好好思考下其实很简单，就是一个数学规律，或许大神和菜鸟的区别就在于此，虽然题目简单但是值得我们去思考和延伸..........

-----------------AC代码----------------------------------

菜鸟方法：

#include<stdio.h>
#define MAX 101
int main()
{
	int a[MAX],x,i,j,k,n,m,y;
	scanf("%d",&m);
	for(y=0;y<m;y++)
	{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		a[i]=1;
	}
	k=1;
	while(k<=n)
	{
		for(j=k;j<=n;j+=k)
		{
			 a[j]=-a[j];
		}
		k++;
	}
	x=0;
	for(i=1;i<=n;i++)
	  if(a[i]==-1) x++;
	printf("%d\n",x);
    }
	return 0;
}

大神方法：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>


int main()
{
    int n,x,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
       scanf("%d",&x);
       printf("%d\n",(int)sqrt((double)x));
       
    }
    system("pause");
    return 0;
}