在OI競賽中，需要判斷一個數(shù)是否為質(zhì)數(shù)的情況很常見，那么如何才能更好的來判斷呢？

        首先我們就從質(zhì)數(shù)的定義入手吧，那么判斷的區(qū)間就應(yīng)該在（1，n）開區(qū)間中所有的自然數(shù)。

        接下來重點來了，我們要讓縮小判斷的范圍，讓程序的運算更快一些。

        對任意合數(shù)n，根據(jù)定義可以設(shè)n=p*q(p<=q)則p<=根號n，從而若n>1且不是素數(shù)，則它的最小素因子一定不超過p,從而不超過根號n。

        所以判斷的范圍縮小到了（1，根號n] 左開右閉區(qū)間中所有的自然數(shù)。

        這樣就成功的將復(fù)雜度從O(n)降到了O(根號n)。

        這樣就可以了嗎？我們再來看一遍定義，質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。

        好了到這里就是網(wǎng)絡(luò)上大部分出現(xiàn)的質(zhì)數(shù)判斷的方法了。

        但是在這里小編還想繼續(xù)優(yōu)化一下。如果一個數(shù)是大于1的偶數(shù)那么它一定被2整除，也肯定不是質(zhì)數(shù)。那對于基數(shù)來說，自然不需要再判斷所有的偶數(shù)是否可以整除了。

        這樣循環(huán)變量每次自增2，把運行次數(shù)又縮短到了原來的一半。

        到這為止，是目前小編能力以內(nèi)能想到最優(yōu)的解法了，如果你還有什么更好的解法，隨時歡迎大家和我交流。