Решение задач №25 ЕГЭ информатика (Обработка целых чисел. Проверка делимости. Python)
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)

Слайд 1

Решение задачи 25 ЕГЭ Тема : Обработка целых чисел. Проверка делимости Что проверяется: Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации. Дрынова Светлана Викторовна

Слайд 2

Что нужно знать : можно использовать простой перебор без оптимизации; пусть необходимо перебрать все целые числа на отрезке [ a ; b ] и подсчитать, для скольких из них выполняется некоторое условие; общая структура цикла перебора записывается так ( Python ): count = 0 for n in range(a, b+1): if условие выполнено : count += 1 print( count ) проверку условия удобно оформить в виде функции, возвращающей логическое значение ( True / False ), но можно этого и не делать

Слайд 3

проверить делимость числа n на число d можно с помощью операции взятия остатка от деления n на x : если остаток равен 0, число n делится на x нацело проверка делимости на языке Python выглядит так: if n % d == 0: print ("Делится") else : print ("Не делится") для определения числа делителей натурального числа n можно использовать цикл, в котором перебираются все возможные делители d от 1 до n , при обнаружении делителя увеличивается счётчик делителей: count = 0 for d in range(1, n+1): if n % d == 0: count += 1 print ( count ) # вывести количество делителей

Слайд 4

перебор делителей можно оптимизировать, учитывая, что наименьший из пары делителей, таких что a  b = n , не превышает квадратного корня из n ; нужно только аккуратно обработать случай, когда число n представляет собой квадрат другого целого числа (можно не оптимизировать для нахождения количества делителей); если требуется определить не только количество делителей, но и сами делители, нужно сохранять их в массиве в языке Python удобно использовать динамический массив: сначала он пуст, а при обнаружении очередного делителя этот делитель добавляется в массив: divs = [] for d in range (1, n +1): # перебор всех возможных делителей if n % d == 0: # если нашли делитель d divs . append ( d ) # то добавили его в массив

Слайд 5

простое число n делится только на 1 и само на себя, причём единица не считается простым числом; таким образом, любое простое число имеет только два делителя для определения простоты числа можно считать общее количество его делителей; если их ровно два, то число простое, если не два – не простое: nDel = 0 # количество делителей числа for d in range (1, n +1): # все возможные делители if n % d == 0: nDel += 1 # нашли ещё делитель if nDel == 2: print( " Число простое " ) else: print ( "Число составное" )

Слайд 6

работу программы можно ускорить: если уже найдено больше двух делителей, то число не простое и можно досрочно закончит работу цикла с помощью оператора break : nDel = 0 # количество делителей числа for d in range (1, n +1): # все возможные делители if n % d == 0: nDel += 1 # нашли ещё делитель if nDel > 2: # уже не простое число break # досрочный выход из цикла if nDel == 2: print ( "Число простое" ) else : print ( "Число составное" ) другой вариант – считать количество делителей числа на отрезке [2; n– 1]; как только хотя бы один такой делитель будет найден, можно завершить цикл, потому что число явно не простое:

Слайд 7

Задача 1. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Решение 1. Для того чтобы вообще избавиться от работы с дробными числами, удобно заменить условие d <= sqrt (n) на равносильное условие, использующее только целые значения: d*d <= n ; при этом, правда, придётся заменить цикл for на while и вручную увеличивать переменную d в конце каждой итерации цикла divCount = 2 # нужное количество делителей for n in range (174457, 174505+1): divs = [] d = 2 while d*d <= n: if n % d == 0: divs.append ( d ) if n//d > d: divs.append ( n//d ) if len ( divs ) > divCount : break d += 1 if len ( divs ) == divCount : print ( * divs )

Слайд 8

Решение 2. Так как здесь нам нужно выводить все делители, кроме единицы и самого числа, в цикле перебора делителей начинаем с 2 и включаем  N, если очередной делитель d –это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей ( d , x // d ): from math import sqrt divCount = 2 # нужное количество делителей for n in range(174457, 174505+1): divs = [] q = int (sqrt(n)) for d in range(2,q+1): if n % d == 0: if d == n//d: divs = divs + [d] else: divs = divs + [d, n//d] if len ( divs ) > divCount : break if len ( divs ) == divCount : print( * divs )

Слайд 9

Решение 3. Можно построить массив делителей на языке Python можно и с помощью генератора списка: for n in range ( 174457; 174505 +1): divs = [d for d in range(1, n+1) if n % d == 0] if len ( divs ) = = 2 : print( * divs ) Аналогично можно построить массив делителей, удовлетворяющих заданному условию, например, всех чётных делителей: for n in range( 174457 , 174457 +1): divs = [d for d in range(1, n+1) if n % d == 0 and d % 2 == 0 ] if len ( divs ) == 4 : print( * divs )

Слайд 10

Решение 4. ещё один вариант программы (с функцией, которая возвращает массив делителей): def allDivisors (n): divs = [] for d in range(1,n+1): if n % d == 0: divs.append (d) return divs for n in range( 174457; 174505 +1): divs = allDivisors (n) if len ( divs ) == 2 : print( * divs )

Слайд 11

Решение 5. (программа без массива): учитывая, что в этой задаче нас интересуют только два делителя, можно вместо массива использовать две дополнительных переменные for i in range (174457, 174505+1): k = 0; for j in range (2, i ): if i % j == 0: k = k + 1; if k == 1: d1 = j if k == 2: d2 = j if k == 2: print( d1, d2 )

Слайд 12

Задача 2.Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [3532000; 3532160], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку. from math import sqrt count = 0 for n in range(3532000, 3532160+1): prime = True for d in range(2, round(sqrt(n))): if n % d == 0: prime = False break if prime: count += 1 print( count, n ) Решение 1.

Слайд 13

Решение 2. компактное решение, использующее встроенную функцию all – она возвращает логическое значение T rue , если все элементы переданного ей списка равны T ru e ; возвращает F alse , если хотя бы один из них равен F alse ( если у 'n' нет делителей от 2 до корня из n т.е. все 'd' дают остаток отличный от нуля): count=0 for n in range(3532000,3532160+1): if all( n%d !=0 for d in range(2,round(n**0.5)+1) ): count+=1 print ( count,n )

Слайд 14

Решение 3. вариант с функцией isPrime , которая возвращает логическое значение True (истина) для простых чисел и False (ложь) для составных: from math import sqrt def isPrime (n): for d in range(2, round(sqrt(n)+1) ): if n % d == 0: return False return True count = 0 for n in range(3532000, 3532160+1): if isPrime (n): count += 1 print( count, n )