編程c語言-i<=sqrt(n);這種情況為什麼也可以判斷是不是素數？

i<=sqrt(n);這種情況為什麼也可以判斷是不是素數？

i <n;這種情況就是用 n 分別除以2，3，……,一直到小於n，如果都除不盡的話，就說n是素數。但實際上不用那麼麻煩的，比如i<=n/2;這種情況，只需要判斷到它的一半就可以了，因為一個數去除以比它的一半還要大的數一定除不盡的，所以不用再判斷了。可是i<=sqrt(n);這種情況我就奇怪了，老想不通這種情況為什麼也可以判斷？

最佳回答：

根據素數的定義反推：因為如果一個數不是素數那麼它一定是兩個數的乘積。 n = sqrt(n) * sqrt(n),假設n是i*j,那麼i和j一定有一個是<= sqrt(n) ,另一個>=sqrt(n)，因次只看較小那個除數存不存在就可以判斷n是否素數。