Егэ проверка на делимость

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Подготовка к ЕГЭ. Разбор заданий № 17 «Проверка делимости чисел.» (раздел Программирование).

Автор: Окунева Надежда Евгеньевна

Проверяемые элементы содержания: Умение составить алгоритм обработки числовой последовательности и записать его в виде простой программы (10– 15 строк) на языке программирования

Проверяемые умения или способы действий: Проверяет умение написать простую переборную программу, на языке программирования, содержащую цикл и ветвление. (повышенный уровень, время – 15 мин)

→ скачать материал

Что нужно знать:

Цикл — разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций. Последовательность инструкций, предназначенная для многократного исполнения, называется телом цикла. Единичное выполнение тела цикла называется итерацией. Выражение, определяющее, будет в очередной раз выполняться итерация или цикл завершится, называется условием выхода или условием окончания цикла. Переменная, хранящая текущий номер итерации, называется счётчиком цикла.2

Ветвление – (условный оператор) — оператор, конструкция языка программирования, обеспечивающая выполнение определённой команды (набора команд) только при условии истинности некоторого логического выражения, либо выполнение одной из нескольких команд (наборов команд) в зависимости от значения некоторого выражения.

Алгоритм решения:

1. Определить начальные значения входных переменных: k, m, где k – искомое количество чисел из заданного диапазона [a, b], удовлетворяющих заданному условию; k = 0 m – minimax, т.е. если осуществляется поиск минимального значения, то m < a, иначе, при поиске максимального значения m > b.

2. Организовать внешний цикл for, где i изменяется в диапазоне от a до b.

3. Организовать каскад вложенных ветвлений if для осуществления проверки заданных условий:
a. проверка делимости (возможны логические операции or и and);
b. проверка неделимости (применяется логическая операция and);
c. проверка minimaxа.

Примеры заданий:

Вариант № 1

Рассматривается множество целых чисел, принадлежащих числовому отрезку [800; 5900], которые делятся на 17 и не делятся на 2, 3, 5. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Вариант № 2

Рассматривается множество целых чисел, принадлежащих числовому отрезку [4197; 9182], которые делятся на 5 и не делятся на 6, 10, 13, 16. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Связанные страницы:

Проверка делимости чисел¹

Разбор задания № 17 КЕГЭ 2021

(соответствует за да нию № K4)

Проверяемые элементы содержания: Умение создавать собственные программы (20–40 строк) для
обработки целочисленной информации.

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

(повышенный уровень, время – 15 мин)

Что нужно знать:

¹ Разбор
заданий представлен на языке программирования Python 3.7.4 2

https://ru.wikipedia.org/wiki/Цикл (программирование)

³ 
Ветвление (программирование) — Википедия

⁴ 
Wiki. Целая часть

⁵ 
Wiki. Дробная часть

Информационные ресурсы:

1.     Теория:
Программирование циклических алгоритмов;
Программирование разветвляющихся алгоритмов.

2.    
Задания
для тренировки: ЕГЭ−2021, информатика

За да ние № 17 (ФИПИ ДЕМО КЕГЭ-2021)

Ответ:
1568
7935

Разбор заданий
№ 17. Готовимся к итоговой аттестации 2021.
Лещинер, В.Р.^[1]

Ответ:
80
5899

Ответ:
71
5833

Задание № 2 (27610)

Ответ:
459
9175

Ответ:
321
1845

Ответ:
446
9163

Ответ:
284
7525

Ответ:
81015893

Ответ:
85
3555

Ответ:
1628
1428

Ответ:
42
5995

Ответ:
94
9997

Ответ: 6
7410

Ответ:
73
13889

Ответ:
119
6391

Ответ:
117
12274

Ответ: 4
5624

Ответ:
8613881

Ответ:
1483
1017

Ответ:
19
4191

Ответ:
965
4671

Ответ:
1701
9205

Ответ:
212
1780

Слайд 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 )

Всем привет! Добрались мы до 25 задания из ЕГЭ по информатике 2023.

Рассмотрим типовые задачи, а так же новые формулировки 25 задания из ЕГЭ по информатике 2023.

Приступаем к первой классической задаче.

Задача (ЕГЭ по информатике, Демо 2022)

Пусть M – сумма минимального и максимального натуральных делителей
целого числа, не считая единицы и самого числа. Если таких делителей
у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 700 000,
в порядке возрастания и ищет среди них такие, для которых значение M
оканчивается на 8. Выведите первые пять найденных чисел
и соответствующие им значения M.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной
строке сначала выводится само число, затем – значение М.
Строки выводятся в порядке возрастания найденных чисел.

Количество строк в таблице для ответа избыточно.

Решение:

На ЕГЭ по информатике 2023 удобно писать программы на языке Python.

import math
count=0
for i in range(700001, 800000):

    b=0
    
    for j in range(2, int(math.sqrt(i)) + 1):
        if i%j==0:
            b=i//j
            break
    
    
    if  b==0: M=0
    else: M=j+b

    if M!=0 and M%10==8:
        count=count+1
        print(i, M)

    if count==5: break

В данной программе перебираются числа в цикле for, начиная с 700001.

Переменная b — считается наибольшим делителем числа i. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно). Ищем тем самым наименьший делитель.

Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.

Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа. А вот то число (так же делитель d4), на которое умножается d1, чтобы получить A, будет находиться после корня A.

Получается, что у каждого делителя есть своя пара. У единицы — это само число. Причём один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).

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

После того, как мы нашли наименьший делитель (он будет сидеть в переменной j) и наибольший делитель b, выходим из второго цикла for.

Если переменная b осталась равна нулю, то, значит, у числа i нет указанных делителей, и переменная M должна равняться 0. Если b не равна нулю, то M=j+b.

Проверить, на что оканчивается число, можно узнав остаток от деления числа на 10.

Переменная count следит, чтобы было распечатано ровно 5 чисел, которые удовлетворяют условию задачи.

Ответ:

Задача (Стандартная)

Напишите программу, которая перебирает целые числа, большие 550 000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом.

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

Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.

Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.

Решение:

Здесь мы ищем наибольший делитель числа, как и в прошлом решении.

import math

def Pr(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i==0: return False
    return True


count=0
for i in range(550001, 1000000):

    b=0
    
    for j in range(2, int(math.sqrt(i)) + 1):
         if i%j==0:
            b=i//j
            break


    if not(Pr(b)):
        count=count+1
        print(i, b)

    if count==6: break

Чтобы проверить число, является ли оно простым, напишем функцию Pr(). Там мы проходим до корня числа. Если не встретился не один делитель, значит, число простое — возвращаем True. Если до корня хотя бы один делитель встретили — возвращаем False.

Ответ:

Задача (Ровно 4 различных делителя)

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [258274; 258297], числа, имеющие ровно 4 различных делителя. Выведите для каждого найденного числа два наибольших делителя в порядке возрастания.

Решение:

import math

for i in range(258274, 258298):
    a=[]
    for j in range(1, int(math.sqrt(i))+1):
        if i%j==0:
            a.append(j)
            b=i//j
            if j!=b:
                a.append(b)

    if len(a)==4:
        a.sort()
        print(a[2], a[3])

Здесь для каждого числа i заводим массив a, где будем сохранять все его делители. Идём как всегда до корня. Если мы нашли делитель, мы добавляем его в массив a c помощью команды append и ищем его «брата». Второй делитель («брат») не должен равняться самому делителю j, т.к. нам сказали, что все делители должны быть различны. Одинаковые делители j и b могут получится, если из нашего числа i извлекается целый корень. Ведь для делителя √i является парой этот же делитель ( √i* √i=i).

После прохождения внутреннего цикла (с переменной j) в массиве a будут сидеть все делители числа i. Если их ровно 4, то сортируем массив a и выводим на экран два наибольших.

Ответ:

Задача (Крепкий орешек)

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [4234679; 10157812] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Решение:

import math

for i in range(4234679, 10157813):
    if int(math.sqrt(i))**2 == i:
        a=[]
        for j in range(2, int(math.sqrt(i))+1):
            if i%j==0:
                a.append(j)
                b=i//j
                if j!=b:
                    a.append(b)
        if len(a)==3:
            a.sort()
            print(i, a[2])

Как у нас могут быть три различных нетривиальных делителя, когда делители идут, как мы выяснили, парами? Это может быть, когда существует целый корень из этого числа. Тогда в паре два числа будут одинаковыми (√i* √i = i). Поэтому в этой задаче нас интересуют числа из которых извлекается елый корень.

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

Далее, решаем, как и в прошлый раз.

Ответ:

Задача (ЕГЭ по информатике, 20.06.22)

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;

— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответсвуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10⁸, найдите все числа, соответствующие маске 1234*7, делящиеся на 141 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 141.

Решение:

Здесь самый главный момент заключается в том, что есть верхняя граница 10⁸. Т.е. самое большое число, которое нужно рассмотреть 1234[999]7 <= 10⁸ = 100000000. Нижняя граница тоже задана, когда вместо звёздочки ни одной цифры не будет 12347.

i=12347

#Вместо звёздочки ноль разрядов
if i%141==0:
    print(i, i//141)

#Вместо звёздочки один разряд
for x in '0123456789':
    s = '1234' + x + '7'
    i=int(s)
    if i%141==0:
        print(i, i//141)

#Вместо звёздочки два разряда
for x in '0123456789':
    for y in '0123456789':
        s = '1234' + x + y + '7'
        i=int(s)
        if i%141==0:
            print(i, i//141)

#Вместо звёздочки три разряда
for x in '0123456789':
    for y in '0123456789':
        for z in '0123456789':
            s = '1234' + x + y + z + '7'
            i = int(s)
            if i%141==0:
                print(i, i//141)

Таким образом, нужно рассмотреть, когда вместо звёздочки ноль разрядов, один разряд, два разряда и три разряда.

Каждый разряд перебираем как цифры (символы). Формируем строку s, а затем её переводим в тип int.

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

Ответ: