(hdu step 2.1.2)How many prime numbers(判斷一個數是否是質數)

題目：

How many prime numbers

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 8513 Accepted Submission(s): 2716 Problem DescriptionGive you a lot of positive integers, just to find out how many prime numbers there are. InputThere are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2. Output
For each case, print the number of prime numbers you have found out. Sample Input

3
2 3 4

Sample Output

2

Authorwangye SourceHDU 2007-11 Programming Contest_WarmUp Recommend威士忌

題目分析：

判斷一個數是否是素數。這道題可以用很多種方法做：定義法、歐拉篩法、埃拉托尼斯篩法來做。本題使用

定義法來做。

關於素數的一些知識點：

第一，對於一個自然數N，只要能被一個非1非自身的數整除，它就肯定不是素數，所以不
必再用其他的數去除。
第二，對於N來說，只需用小於N的素數去除就可以了。例如，如果N能被15整除，實際
上就能被3和5整除，如果N不能被3和5整除，那麼N也決不會被15整除。
第三，對於N來說，不必用從2到N-1的所有素數去除，只需用小於等於√N(根號N)的所有素數去除就可以了。這一點可以用反證法來證明：
如果N是合數，則一定存在大於1小於N的整數d1和d2，使得N=d1×d2。
如果d1和d2均大於√N，則有：N＝d1×d2>√N×√N＝N。
而這是不可能的，所以，d1和d2中必有一個小於或等於√N。

代碼如下：

/*
 * b.cpp
 *
 *  Created on: 2015年1月30日
 *      Author: Administrator
 */

#include 
#include 
#include 



using namespace std;

/**
 * 判斷一個數是否是質數(素數)
 */
bool isPrime(int n){
	if(n == 1 || n == 0){//0和1既不是合數也不是素數
		return false;
	}

	int i;
	for(i = 2 ; i <= sqrt(n*1.0) ; ++i){//判斷一個數是否是素數只需要到<=根號n即可.這道題如果上界取到n會TLE
		if(n%i == 0){//如果它能整出其中一個因子
			return false;//則表明他不是素數
		}
	}

	return true;
}

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int ans = 0;
		int i;
		for(i = 0 ; i < n ; ++i){
			int temp;
			scanf("%d",&temp);
			if(isPrime(temp) == true){
				ans++;
			}
		}

		printf("%d\n",ans);
	}

	return 0;
}