اگر عدد $n$ اول ​نباشد می‌توان آن را به صورت ​$n = ab$ نوشت که در آن $a$ و $b$ اعدادی بزرگتر از یک هستند. از طرفی ​اگر $n$ برابر $ab$ باشد $min(a, b) \leq \sqrt{n}$ ​خواهد بود. بنابراین ​هر عدد ​مرکب مانند $n$ حداقل یک مقسوم الیه بین $2$ تا $\sqrt{n}$ ​دارد بنابراین اول بودن ​یک عدد ​را می‌توان با استفاده از الگوریتمی از مرتبه زمانی $O(\sqrt{n})$ فهمید.

Primality_test.cpp

bool is_prime(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}