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

Содержание

1 1 ответ 1
2 Всё ещё ищете ответ? Посмотрите другие вопросы с метками python или задайте свой вопрос.

Перебор делителей – это алгоритм, применяемый для определения, является ли натуральное число простым, или оно является сложным, то есть составным.

Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.

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

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

Число 2 является простым, но при этом оно делится на 2. Цикл while определил бы двойку как составное число, что неправильно. Поэтому для числа 2 необходима отдельная проверка.

Программа дойдет до последней строчки кода, только если не был найден ни один делитель. Если это так, значит число составное.

Пример функции, определяющей является ли число простым:

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

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

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

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

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

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

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

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

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

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

ПРОГРАММА:

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

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

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 можно использовать цикл for вместе с функцией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.

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

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

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

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

Доброй ночи! Только начал обучение, и тут домашка которую я не могу сделать 6 часов) Домашка собственно звучит так "Написать функцию is_prime, принимающую 1 аргумент — число от 0 до 1000, и возвращающую True, если оно простое, и False — иначе."

a = int(input("Enter a number: ")) print(is_prime(a))