Wikioi 天梯 素數判定（1430）

題目描述 Description

質數又稱素數。指在一個大于1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。

素數在數論中有着很重要的地位。比1大但不是素數的數稱為合數。1和0既非素數也非合數。質數是與合數相對立的兩個概念，二者構成了數論當中最基礎的定義之一。基于質數定義的基礎之上而建立的問題有很多世界級的難題，如哥德巴赫猜想等。算術基本定理證明每個大于1的正整數都可以寫成素數的乘積，并且這種乘積的形式是唯一的。這個定理的重要一點是，将1排斥在素數集合以外。如果1被認為是素數，那麼這些嚴格的闡述就不得不加上一些限制條件。

概念

隻有1和它本身兩個約數的自然數，叫質數(Prime Number)。（如：由2÷1=2，2÷2=1，可知2的約數隻有1和它本身2這兩個約數，是以2就是質數。與之相對立的是合數：“除了1和它本身兩個約數外，還有其它約數的數，叫合數。”如：4÷1=4，4÷2=2，4÷4=1，很顯然，4的約數除了1和它本身4這兩個約數以外，還有約數2，是以4是合數。）

100以内的質數有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25個質數。

注：（1）1既不是質數也不是合數。因為它的約數有且隻有1這一個約數。

（2）2和3是所有素數中唯一兩個連着的數 ．

輸入描述 Input Description

第一行輸入一個正整數n，n<=30000

輸出描述 Output Description

如果該數是質數，則輸出\t

否則輸出\n

樣例輸入 Sample Input

輸入樣例１

13

輸入樣例２

8

樣例輸出 Sample Output

樣例輸出１

\t

樣例輸出２

\n

資料範圍及提示 Data Size & Hint

c或c++的初學者注意，"＼"的意思

素數的定義題裡說的很清楚了~~

判定少量素數一般用樸素判斷，即枚舉因子可能存在的區域，若除一、本身以外存在其他因子，則不是素數；

較多時使用篩法（這裡不給予詳細說明）；

太多時……就要利用其他的條件和推導來進行優化……（這種題其實考的就不是素數判定了）

樸素判斷就是……（上面說過了）……

下面就說一點，枚舉因子時隻需要枚舉根号n以内的整數即可。

一個數的因子肯定比他小……

一個數的最少有兩個因子……

一個數分解成兩個數相乘時，這兩個數是這個數的因子……

這兩個因子無非三種情況：a<根号n,b>根号n；a=根号n,b=根号n；a>根号n,b<根号n。

懂了嗎……？

是以根号n的閉區間内如果沒有n的因子，那麼以外一定也沒有。

因為如果根号n以外有n的因子，那麼與他配對的因子早在根号n以内出現過了……

廢了這麼多話，就為了把O(n)優化成O(sqrt(n))……

其實這結論對有些人來說都不用證……

神犇們的證明是——“大家看，這個結論…顯而易見！”

算法描述：

讀入n；

枚舉sqrt(n)以内整數，不包括1；

若整除n，傳回否，退出程式，否則繼續枚舉；

若枚舉結束，則傳回是。

Program pjudge;
Var
	x:longint;
	
Function sushu(bb:longint):boolean;
	var a:longint;
	begin
		if (bb=1)or(bb=0) then exit(false);
		for a:=2 to trunc(sqrt(bb)) do
			if (bb mod a)=0 then exit(false);
		exit(true);
	end;
	
Begin
	readln(x);
	if sushu(x) then
	writeln('\t')
	else writeln('\n');
End.