質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無(wú)限個(gè)。
質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。
在OI競(jìng)賽中，需要判斷一個(gè)數(shù)是否為質(zhì)數(shù)的情況很常見，那么如何才能更好的來(lái)判斷呢？
首先我們就從質(zhì)數(shù)的定義入手吧，那么判斷的區(qū)間就應(yīng)該在（1，n）開區(qū)間中所有的自然數(shù)。
接下來(lái)重點(diǎn)來(lái)了，我們要讓縮小判斷的范圍，讓程序的運(yùn)算更快一些。
對(duì)任意合數(shù)n，根據(jù)定義可以設(shè)n=p*q(p<=q)則p<=根號(hào)n，從而若n>1且不是素?cái)?shù)，則它的最小素因子一定不超過p,從而不超過根號(hào)n。
所以判斷的范圍縮小到了（1，根號(hào)n] 左開右閉區(qū)間中所有的自然數(shù)。
這樣就成功的將復(fù)雜度從O(n)降到了O(根號(hào)n)。
這樣就可以了嗎？我們?cè)賮?lái)看一遍定義，質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。
好了到這里就是網(wǎng)絡(luò)上大部分出現(xiàn)的質(zhì)數(shù)判斷的方法了。
但是在這里小編還想繼續(xù)優(yōu)化一下。如果一個(gè)數(shù)是大于1的偶數(shù)那么它一定被2整除，也肯定不是質(zhì)數(shù)。那對(duì)于基數(shù)來(lái)說，自然不需要再判斷所有的偶數(shù)是否可以整除了。
這樣循環(huán)變量每次自增2，把運(yùn)行次數(shù)又縮短到了原來(lái)的一半。
到這為止，是目前小編能力以內(nèi)能想到最優(yōu)的解法了，如果你還有什么更好的解法，隨時(shí)歡迎大家和我交流。
聯(lián)系客服
