Проверку числа на простоту оформим в виде функции, которая будет возвращать True для простых чисел и False для составных.
Наивный алгоритм заключается в том, что будем перебирать числа, начиная с 2, пока не не найдем делитель числа n. Если этот делитель будет равен n, то число будет простым, иначе у n есть нетривиальный делитель и число n будет составным.
Запишем алгоритм в виде функции IsPrime (по-английски простое число — prime number, составное число — composite number).
В данной записи алгоритма реализована идея линейного поиска с барьерным элементом. Мы хотим найти наименьший делитель числа n. Для этого берем число d и пока n не делится на d переходим к следующему возможному делителю. Алгоритм остановится на числе, которое будет делителем числа n. Если алгоритм остановился на числе n, то число n простое, иначе — составное.
Сложность этого алгоритма — O(n).
Однако данный алгоритм можно оптимизировать, если заметить, что у любого составного числа есть собственный (то есть не равный 1) делитель, не превосходящий квадратного корня из числа. Это позволит сократить сложность алгоритма до O(n√):
7.9 Простые числа. «Поколение Python»: курс для начинающих. Курс Stepik
Соответственно, такой алгоритм заканчивает работу либо при нахождении делителя, либо если проверяемый делитель станет больше корня из 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 с каждым проходом цикла).
Решение простых задач на python | Високосный ли год
В списке значений могут быть выражения различных типов, например:
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 — признак конца ввода):
Или же, если требуется найти произведение только отрицательных чисел:
Может потребоваться подсчитать количество определенных (например, четных) чисел:
Например, это может понадобиться для того, чтобы найти среднее арифметическое только четных чисел:
Источник: infopedia.su
Программа Python для проверки того, является ли число простым или нет
Когда два целых числа умножаются, получается произведение. Факторы продукта – это числа, которые мы умножаем.
В математике коэффициент – это число или алгебраическое выражение, которое поровну делит другое число или выражение, не оставляя остатка.
Простое число:
Простое число – это положительное целое число больше 1, не имеющее других переменных, кроме 1 и самого числа. Поскольку у них нет других переменных, числа 2, 3, 5, 7 и т. Д. Являются простыми числами.
Учитывая число, задача состоит в том, чтобы проверить, является ли данное число простым или нет.
Примеры:
Пример 1:
Вход:
number =5
Выход:
The given number 5 is a prime number
Пример 2:
Вход:
number =2
Выход:
The given number 2 is not prime number
Программа для проверки простого числа в программировании на Python
Ниже приведены способы проверить, является ли данное число простым или нет:
Изучите больше примеров, связанных с концепциями Python, из Руководства по примерам программирования Python и получите повышение от новичка до профессионального уровня программиста в языке программирования Python.
1) Использование цикла for для перехода от 2 к N-1 с использованием флаговой или временной переменной
Чтобы увидеть, есть ли какие-либо положительные делители, кроме 1 и самого числа, мы делим входное число на все числа в диапазоне от 2 до (N – 1).
Если делитель найден, отображается сообщение «число не является простым числом», в противном случае отображается сообщение «число является простым числом».
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
python_lessons / python_coursera / 4_week / 55_Проверка числа на простоту.py /
Code definitions
Code navigation index up-to-date
- Go to file T
- Go to line L
- Go to definition R
- Copy path
- Copy permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Cannot retrieve contributors at this time
26 lines (22 sloc) 785 Bytes
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents Copy raw contents
Copy raw contents
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| «»» |
| Дано натуральное число n>1. |
| Проверьте, является ли оно простым. |
| рограмма должна вывести слово YES, |
| если число простое и NO, если |
| число составное. Решение оформите |
| в виде функции IsPrime(n), которая |
| возвращает True для простых чисел и |
| False для составных чисел. Количество |
| действий в программе должно быть |
| пропорционально квадратному корню из n. |
| «»» |
| def isPrime ( n ): |
| d = 2 |
| while d * d |
| d += 1 |
| return d * d > n |
| n = int ( input ()) |
| if isPrime ( n ): |
| print ( ‘YES’ ) |
| else : |
| print ( ‘NO’ ) |
- Copy lines
- Copy permalink
- View git blame
- Reference in new issue
Источник: github.com