程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> (hdu step 2.1.2)How many prime numbers(判斷一個數是否是質數)

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

編輯:C++入門知識

(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;
}







  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved