Опр:Нат.число n>1 прост, если делится только на себя и на 1, n|n, 1|n, где 1,n-тривиал. делит. Опр: Нат.число n>1 -прост, есл имеет только тривиальные делители. Опр: Нат.число n>1 - составное, если имеет нетривиал.делители. n=n1*n2, 1<n1<n и 1<n2<n
Крит простоты числа: Если нат число n>1 не делтся ни на одно простое число p ≤ корень n, то n-простое. Док-во: Пусть все усл выпол, но n-сост, n=n1*n2. Оно сост => имеет прост делитель. Пусть n1<= корень n. q|n1, n1|n=>q|n И q<n1<=корень n. А значит наше предполож, что n-сост неверно. n-прост число.
Решето Эратосфена. Выписываем все нечет числа м\у 3 и n, вычеркиваем каждое 3, каждое 5 итд, пока не дойдем до n. Если вычеркивать каждое p-ое число, то надо начинать отсчет с числа p+2, даже если оно было вычернкуто.
