|
|
практикумы по языку Питон. Питон. Практикум Загидуллин Наиль Рашитович мбоу сош 2 Оглавление Введение в Питон 4 Команда вывода 4
Простые числа
Урок 3.6
Простое число — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p
Теорема Евклида (Основная теорема арифметики)
Каждое целое число можно представить единственным образом в виде произведения простых чисел (факторизация).
|
|
Тест простоты. (алгоритм простоты)
Самый простой алгоритм
a = int(input("Введите число: "))
k = 0
for i in range(2, a):
if (a % i == 0):
k = k+1
if (k <= 0):
print("Число простое")
else:
print("Число не является простым")
Чтобы сократить число переборов, достаточно проверить делители из промежутка 2..n//2+1 (или более точно 2.. n**(0.5))
…
for i in range(2, a//2+1):
…
|
Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.
def isprime(n):
if n <= 1: return False
elif n == 2: return True
else:
for i in range(3, n//2+1,2):
if n%i == 0:
return False
break
else:
return True
print(isprime(12))
Более компактное решение:
num = int(input())
res = [i for i in range(2, num//2+1) if num % i == 0]
print('yes' if len(res) == 0 else 'no')
|
Факторизация числа
import math
number=int(input())
for i in range(2, int(math.sqrt(number)) + 1):
while (number % i == 0):
print(i, end=' ')
number //= i # убираем множитель из числа
if (number != 1): # но один делитель может быть больше корня
print (number)
|
Вывод всех простых чисел до N
n = int(input())
# создаем пустой список для хранения простых чисел
lst = []
# в k будем хранить количество делителей
k = 0
# пробегаем все числа от 2 до N
for i in range(2, n+1):
# пробегаем все числа от 2 до текущего
for j in range(2, i):
# ищем количество делителей
if i % j == 0:
k = k + 1
# если делителей нет, добавляем число в список
if k == 0:
lst.append(i)
else:
k = 0
# выводим на экран список
print lst
|
|
Задание:
Проверьте число 1484631 на простоту
Выполните фактроизацию числа 9973
Выведите все простые числа от 1000 до 2000
|
У рок 3.7
|
Решите задачу «Горошины»
Из трех горошин нельзя построить прямоугольник, а из 4 можно. Из 5 снова нет, из 6 да.
Напишите первые 100 чисел из которых нельзя построить прямоугольник.
Решение.
Нужно вывести первые 100 простых чисел
Вместо for i in range(3, n+1, 2) используем цикл
i = 3
while count < 100:
i+=2
…
count +=1 #если найдено простое число
…
|
Урок 3.8
|
|
Задание
1)Проверьте является ли число а)23921 б) 8128 совершенным?
2)Найдите максимальное число из диапазона от 1000 до 5000, который имеет ровно три нетривиальных делителя.
| |
|
|
Скачать 7.93 Mb.