Проверка числа на простоту в Python

Проверку числа на простоту оформим в виде функции, которая будет возвращать True для простых чисел и False для составных.

Наивный алгоритм заключается в том, что будем перебирать числа, начиная с 2, пока не не найдем делитель числа n. Если этот делитель будет равен n, то число будет простым, иначе у n есть нетривиальный делитель и число n будет составным.

Запишем алгоритм в виде функции IsPrime (по-английски простое число — prime number, составное число — composite number).

def IsPrime(n):

d = 2

while n % d!= 0:

d += 1

return d == n

В данной записи алгоритма реализована идея линейного поиска с барьерным элементом. Мы хотим найти наименьший делитель числа n. Для этого берем число d и пока n не делится на d переходим к следующему возможному делителю. Алгоритм остановится на числе, которое будет делителем числа n. Если алгоритм остановился на числе n, то число n простое, иначе — составное.

Сложность этого алгоритма — O(n).

Однако данный алгоритм можно оптимизировать, если заметить, что у любого составного числа есть собственный (то есть не равный 1) делитель, не превосходящий квадратного корня из числа. Это позволит сократить сложность алгоритма до O(n√):

def IsPrime(n):

d = 2

while d * d <= n and n % d!= 0:

d += 1

return d * d > n

Соответственно, такой алгоритм заканчивает работу либо при нахождении делителя, либо если проверяемый делитель станет больше корня из n. Чиcло n является простым, если алгоритм закончился по причине того, что проверяемый делитель стал больше, чем корень из n.

ПЕРЕБОР ТОЛЬКО НЕЧЕТНЫХ ДЕЛИТЕЛЕЙ

Сделаем ещё одну оптимизацию — будем перебирать только нечетные делители, если число не делится на два.

def isPrime(n):
if n % 2 == 0:
return n == 2

d = 3

while d * d <= n and n % d!= 0:

d += 2

return d * d > n

ПРОГРАММА:

(0 — признак конца ввода)

sum_int = 0

counter = 0

x = int(input())

while x!= 0:

sum_int += x

counter += 1

x = int(input())

print(sum_int / counter)

ОДНОПРОХОДНАЯ ПРОГРАММА:

summa = 0 summa_2 = 0 kolichestvo = 0 x = int(input()) while x!= 0: summa += x summa_2 += x*x kolichestvo += 1 x = int(input()) srednee = summa/kolichestvo srednee_2 = summa_2/kolichestvo otklonenie = (srednee_2 - srednee**2)**0.5 print('Среднее значение:', srednee, '+-', otklonenie)

Цикл for в Python

Цикл for, также называемый циклом с параметром, в языке Питон богат возможностями. В цикле for указывается переменная и множество значений, по которому будет пробегать переменная. Множество значений может быть задано списком, кортежем, строкой или диапазоном.

Вот простейший пример использования цикла, где в качестве множества значений используется кортеж:

i = 1
for color in 'red', 'orange', 'yellow', 'green', 'cyan', 'blue', 'violet':
print(i, '-th color of rainbow is ', color, sep = '')
i += 1

В этом примере переменная color последовательно принимает значения ‘red’, ‘orange’ и т.д. В теле цикла выводится сообщение, которое содержит название цвета, то есть значение переменной color, а также номер итерации цикла – число, которое сначала равно 1, а потом увеличивается на один (инструкцией i += 1 с каждым проходом цикла).

В списке значений могут быть выражения различных типов, например:

for i in 1, 2, 3, 'one', 'two', 'three':
print(i)

При первых трех итерациях цикла переменная i будет принимать значение типа int, при последующих трех — типа str.

ФУНКЦИЯ RANGE

Как правило, циклы for используются либо для повторения какой-либо последовательности действий заданное число раз, либо для изменения значения переменной в цикле от некоторого начального значения до некоторого конечного.

Для повторения цикла некоторое заданное число раз n можно использовать цикл fo r вместе с функцией range:

for i in range(n):
Тело цикла

В качестве n может использоваться числовая константа, переменная или произвольное арифметическое выражение (например, 2 ** 10). Если значение n равно нулю или отрицательное, то тело цикла не выполнится ни разу.

Если задать цикл таким образом:

for i in range(a, b):
Тело цикла

то индексная переменная i будеть принимать значения от a до b – 1, то есть первый параметр функции range, вызываемой с двумя параметрами, задает начальное значение индексной переменной, а второй параметр — значение, которая индексная переменная принимать не будет. Если же a≥b, то цикл не будет выполнен ни разу. Например, для того, чтобы просуммировать значения чисел от 1 до n можно воспользоваться следующей программой:

sum = 0
for i in range(1, n + 1):
sum += i

В этом примере переменная i принимает значения 1, 2, …, n, и значение переменной sum последовательно увеличивается на указанные значения.

Наконец, чтобы организовать цикл, в котором индексная переменная будет уменьшаться, необходимо использовать функцию range с тремя параметрами. Первый параметр задает начальное значение индексной переменной, второй параметр — значение, до которого будет изменяться индексная переменная (не включая его!), а третий параметр — величину изменения индексной переменной. Например, сделать цикл по всем нечетным числам от 1 до 99 можно при помощи функции range(1, 100, 2), а сделать цикл по всем числам от 100 до 1 можно при помощи range(100, 0, -1).

Более формально, цикл for i in range(a, b, d) при d > 0 задает значения индексной переменной i = a, i = a + d, i = a + 2 * d и так для всех значений, для которых i < b. Если же d < 0, то переменная цикла принимает все значения i > b.

Фильтрация потока чисел

Пусть на вход программы подаются числа, подлежащие обработке, причем из них нужно использовать только те, которые удовлетворяют некоторому условию.

Например, если требуется просуммировать только четные числа, это можно сделать так (0 — признак конца ввода):

sum_even = 0

x = int(input())

while x!= 0:

if x % 2 == 0:

sum_even += x

x = int(input())

print(sum_even)

Или же, если требуется найти произведение только отрицательных чисел:

product = 1

x = int(input())

while x!= 0:

if x < 0:

product *= x

x = int(input())

print(product)

Может потребоваться подсчитать количество определенных (например, четных) чисел:

counter = 0

x = int(input())

while x!= 0:

if x % 2 == 0:

counter += 1

x = int(input())

print(counter)

Например, это может понадобиться для того, чтобы найти среднее арифметическое только четных чисел:

sum_even = 0

counter = 0

x = int(input())

while x!= 0:

if x % 2 == 0:

sum_even += x

counter += 1

x = int(input())

print(sum_even / counter)