首先來看一個最原始的素數判定代碼（改編自菜鳥教程）：

#include <stdio.h>
 
int main()
{
    int n, i, flag = 0;
 
    printf("輸入一個正整數: ");
    scanf("%d",&n);
 
    for(i=2; i<=n-1; ++i)  {
        // 符合該條件不是素數
        if(n%i==0)  {
            flag=1;
            break;
        }
    }
    if(n <=1 ) {
        flag=1; // 1 和 0 不是素數
    }
    if (flag==0)
        printf("%d 是素數",n);
    else
        printf("%d 不是素數",n);
    
    return 0;
}

其實 i 不需要從 2~n-1 進行查找，只需要在 2~sqrt(n) 之間尋找因子，理由如下。

如果我們假設存在正整數 x,y（2 <= x <= y <= n-1）使得 n = x*y，那麼，由於 sqrt(n)^2 = n，x, y 必然是一個在 sqrt(n) 左側，一個在其右側，或者是 x = y = sqrt(n)。

因爲

1. 如果 x, y 都小於 sqrt(n)，那麼 xy 必 < n
   

2. 如果 x, y 都大於 sqrt(n)，那麼 xy 必 > n
   

故原命題得證。