Poszukuję pewnego twierdzenia TPB: Ostatnio przypomniało mi się (albo uroiło), że gdzieś widziałem takie twierdzenie. "Jeżeli liczba naturalna n ma dzielnik pierwszy, to jest on mniejszy od √n". Coś w tym stylu. Istniało coś takiego, a jeżeli tak to gdzie można znaleźć dowód tego twierdzenia i informacje o nim.

Trivial: Weźmy liczbę 7*2 = 14. 3<√14<4, ale liczba 14 ma dzielnik pierwszy 7>√14. To twierdzenie chyba wygląda w ten sposób: Aby sprawdzić, czy liczba n jest pierwsza wystarczy sprawdzić czy dzieli się przez liczby pierwsze ≤√n.

TPB: No tak

Trivial: Szkic dowodu: Załóżmy, że n da się rozłożyć na iloczyn liczby pierwszej i jakiejś innej liczby: n = n₁n₂. Jaka maksymalnie może być n₁? Jeżeli n₁ > √n to automatycznie n₂ < √n. Sprawdzamy więc te same przypadki w odwrotnej kolejności. Wystarczy więc sprawdzić, czy n dzieli się przez liczby pierwsze ≤ √n.