алгоритм – Why is it that when checking for primality, values ​​are only sorted up to the square root?


Often, tasks for determining the simplicity of a number are solved according to this algorithm – they sort through all the numbers starting from 2 and try to divide the number being checked by each until a zero remainder is encountered. If met, then the number is not prime.

But the enumeration leads to the square root of the number being checked. And I don't understand why this is so? Why can't the divisor occur among numbers greater than the square root of the one being checked?


If the number is not prime, then it has at least two factors that must be less than (or equal to) the root of the original number, otherwise their product would be greater than it, so it makes no sense to sort through the numbers that follow.

Scroll to Top