Особые числа (простые, фибоначи, факториал, палиндромы) —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#16434

Санта Клаус облетает город, в котором стоят дома под номерами, принадлежащими отрезку $[1;1000]$ . В домах, чей номер — простое число, живут дети, которые плохо себя вели весь год, им Cанта Клаус подарок не подарит. Найдите кол-во детей, которые в новогоднюю ночь останутся без подарка.

Показать ответ и решение

def is_prime(n): # функция для проверки, что число - простое
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n != 1 # проверка, что число не равна 1, так как 1 - не простое число

count = 0
for i in range(1, 1001):
    if is_prime(i):
        count += 1
print(count)

Ответ: 168

Ошибка.
Попробуйте повторить позже

Задача 2#22054

Напишите программу, которая ищет количество простых чисел, принадлежащих числовому отрезку $[1000000;5000000]$ .

Показать ответ и решение

Решение 1

Классическое неэффективное решение через перебор, которое умирает на больших диапазонах

def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True
count = 0
for i in range(1000000, 5000000 + 1):
    if is_prime(i): count += 1
print(count)

Решение 2

Эффективное решение задачи с помощью алгоритма «Решето Эратосфена»

def resheto(n):
    a = [1] * (n + 1)
    a[0] = a[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if a[i]:
            for j in range(i, n // i + 1):
                a[i * j] = 0
    return a
print(sum(resheto(5000000)) - sum(resheto(999999)))

Ответ: 270015

Ошибка.
Попробуйте повторить позже

Задача 3#22666

Числа-близнецы $−$ это такие простые числа, которые отличаются друг от друга на 2. Найдите все пары чисел-близнецов в диапазоне [2 500 000; 3 500 000], сумма которых будет кратна 50000. В ответ запишите найденные пары, числа в которых записаны по возрастанию.

Показать ответ и решение

def prime(x):  # функция для проверки, что число - простое
if x == 1:return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
ans = 0
flag = True
for i in range(2500000, 3500000+1):
    if prime(i): # проверка, что текущее число - простое
        if flag: # если ранее простое число мы не встречали
            last = i # запоминаем значение последнего встретишевгося нам простого числа
            flag = False # убираем флаг, который отвечал за то, встречалось нам ли ранее просто число
        else: #в ином случае
            if i - last == 2: # если разность между текущим простым числом и тем, что встречали ранее равна 2
                if (last + i) % 50000 == 0: # проверка по условию
                    print(last, i)
            last = i

Ответ: 3149999 3150001

Ошибка.
Попробуйте повторить позже

Задача 4#25785

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[55556;55776]$ , простые числа. Программа должна вывести количество таких чисел.

Показать ответ и решение

def prime(n): # функция для проверки, что число - простое
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
k = 0
for i in range(55556, 55777):
    if prime(i):
        k += 1
print(k)

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 5#27874

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [55556; 55776], простые числа. Программа должна вывести количество таких чисел.

Показать ответ и решение

def is_prime(n):
    flag = True
    for i in range(2, n):
        if (n % i == 0):
            flag = False
            break
    return flag

a = 55556
b = 55776
counter = 0

for i in range(a, b + 1):
    if (is_prime(i)):
        counter = counter + 1

print(counter)

Комментарии к решению

1) В данной задаче удобно написать функцию is_prime(n), которая будет проверять числа на простоту. Если число простое, функция вернёт True, иначе – False. Если в цикле функция вернёт True, то увеличим counter на 1.

$\text{[math]}$

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 6#27876

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [100;100100], простые числа. Программа должна вывести количество таких чисел и максимальное простое число, которое принадлежит данному отрезку.

Показать ответ и решение

a = 100   # Задаем границы цикла
b = 100100
maxim = -1
count = 0   # счетчик
for i in range(a, b + 1):
    flag = True     # Индикатор простоты числа
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            flag = False    # Если есть делитель - число составное
            break
    if (flag): # если текущее число - простое
        count += 1
        if i > maxim:
           maxim = i
print(count, maxim)

$\text{[math]}$

Ответ: 9573 100069

Ошибка.
Попробуйте повторить позже

Задача 7#27878

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [12345;12425], числа, которые в делителях имеют число-палиндром. Программа должна вывести количество таких чисел.

Числа-палиндромы - числа, которые читаются одинаково как справа налево, так и слева направо. Минимальная длина числа-палиндрома равна 2.

Показать ответ и решение

a = 12345 # Задаю границы цикла
b = 12425
count = 0   # Будущий ответ
for i in range(a, b + 1):
    has_div_pal = False    # Имеет ли число делитель-палинром?
    for j in range(1, i + 1):
        if i % j == 0:
            # Число будет палиндромом, если оно читается с 2 сторон одинаково
            # и его длина > 1
            if str(j)==str(j)[::-1] and len(str(j)) > 1:
                has_div_pal = True
                break
            if str(i//j) == str(i//j)[::-1] and len(str(i//j)) > 1:
                has_div_pal = True
                break
    if (has_div_pal): # если у числа есть делитель палиндром
        count += 1
print(count)

$\text{[math]}$

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 8#28547

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[424242;727272]$ , простые числа. Программа должна вывести количество таких чисел.

Показать ответ и решение

def is_prime(n): # функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

result = 0
for i in range(424242, 727272 + 1):
    if is_prime(i):
        result += 1
print(result)

Ответ: 22866

Ошибка.
Попробуйте повторить позже

Задача 9#28549

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[11111;22222]$ , числа, которые в делителях имеют число-палиндром. Программа должна вывести количество таких чисел. Числа-палиндромы — числа, которые читаются одинаково как справа налево, так и слева направо. Минимальная длина числа-палиндрома равна $2$ .

Показать ответ и решение

def f(n): # функция для проверки есть ли у числа делитель - палиндром
    for x in range(1, int(n ** 0.5) + 1):
        if n % x == 0:
            if len(str(x)) > 1 and str(x) == str(x)[::-1]:
                return True
            if x != n // x and len(str(n // x)) > 1 and \
                    str(n // x) == str(n // x)[::-1]:
                return True
    return False

result = 0
for i in range(11111, 22222 + 1):
    if f(i): # проверка есть ли у числа делитель палиндром
        result += 1
print(result)

Ответ: 2503

Ошибка.
Попробуйте повторить позже

Задача 10#29460

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [33456; 72373], простые числа. Программа должна вывести количество таких чисел.

Показать ответ и решение

def is_prime(n): # функция для проверки, что число - простое
    if n == 1: return  False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
k = 0
for x in range(33456, 72374):
    if is_prime(x): # если число - простое
        k += 1
print(k)

Ответ: 3582

Ошибка.
Попробуйте повторить позже

Задача 11#30193

Найти количество простых чисел на промежутке $[13123,321321]$ .

Показать ответ и решение

def prime(n):  # Проверка на простоту
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

counter = 0
for i in range(13123, 321322):
    if prime(i):
        counter += 1
print(counter)

Ответ: 26152

Ошибка.
Попробуйте повторить позже

Задача 12#30199

Найти на промежутке $[157314,853412]$ числа, которые являются квадратами простых чисел. В ответе запишите количество таких чисел и их сумму через пробел.

Показать ответ и решение

Решение 1

def prime(n):# функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


counter, summ = 0, 0
for i in range(157314, 853412 + 1):
    if (int(i ** 0.5) == i ** 0.5) and prime(i ** 0.5): # проверка, что у числа етсь корень и при этом он является простым числом
        counter += 1
        summ += i
print(counter, summ)

Решение 2

def prime(n): # функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

counter, summ = 0, 0
for i in range(int(157314**0.5), int(853412**0.5)+1): # перебираем в пределах значений корней наших чисел
    if (157314 <= i*i <= 853412) and prime(i): # проверка, что число в квадрате будет в пределах перебора и при этом является простым числом
        counter+= 1
        summ += i**2
print(counter, summ)

Ответ: 80 35716880

Ошибка.
Попробуйте повторить позже

Задача 13#30200

Найти на промежутке $[174133,321441]$ числа, которые являются четвертыми степенями простых чисел. В ответе через пробел запишите количество таких чисел и сумму цифр всех чисел.

Показать ответ и решение

def prime(n):# функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def sum_digits(n):  # сумма цифр
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s


counter, summ_digits = 0, 0
for i in range(174133, 321442):
    if (int(i ** 0.25) == i ** 0.25) and prime(i ** 0.25): # если корень четвёртой степени у числа является целым числом и при этом он - простое число
        counter += 1
        summ_digits += sum_digits(i)
print(counter, summ_digits)

Ответ: 1 31

Ошибка.
Попробуйте повторить позже

Задача 14#30205

Назовем число любопытным, если оно представимо в виде произведения $3$ простых чисел, взятых в первой степени. Найти на промежутке $[312311,524321]$ количество любопытных чисел и наибольшее из любопытных чисел. Числа в ответе запишите через пробел.

Показать ответ и решение

def prime(n): # функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def three_prime_divs(n): # функция, которая проверяет можно ли получить число произведением трёх его простых делителей
    a = []
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if prime(i):
                k += 1
                a.append(i)
            if n // i != i and prime(n // i):
                k += 1
                a.append(n // i)
        if k > 3:
            return False
    if k == 3 and a[0] * a[1] * a[2] == n:
        return True  # Произведение трех простых делителей в 1 степени
        # чтобы не посчитать числа, такие как 3 * 3 * 5 * 7
    return False


counter, maxim = 0, 0
for i in range(312311, 524322):
    if three_prime_divs(i):
        counter += 1
        maxim = max(maxim, i)
print(counter, maxim)

Ответ: 44151 524318

Ошибка.
Попробуйте повторить позже

Задача 15#30210

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

Показать ответ и решение

def prime(x): # функция для проверки, что число - простое
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

for i in range(5537177, 5537236+1):
    if prime(i):
        print(i)

Ответ: 5537201 5537221

Ошибка.
Попробуйте повторить позже

Задача 16#30213

Среди целых чисел, принадлежащих числовому отрезку [131590; 591584], найдите числа, которые являются простыми. Ответом будет сумма цифр найденных чисел.

Показать ответ и решение

def prime(x):# функция для проверки, что число - простое
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(131590, 591584+1):
    if prime(i): # проверка является ли число - простым
        ans += sum([int(j) for j in str(i)]) # прибавляем сумму цифр простого числа
print(ans)

Ответ: 948492

Ошибка.
Попробуйте повторить позже

Задача 17#30218

Числа-близнецы — это такие простые числа, которые отличаются друг от друга на 2. Найдите все пары чисел-близнецов в диапазоне [500 000; 1 500 000]. В ответе запишите количество найденных пар.

Показать ответ и решение

def prime(x):# функция для проверки, что число - простое
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
last = 0
flag = True # флаг, отвечающий за то, встречали ли мы ранее простое число
for i in range(500000, 1500000+1):
    if prime(i): # если число - простое
        if flag: # если ранее простое число мы не встречали
            last = i # записываем значение текущего числа в переменную
            flag = False # убираем флаг
        else: # если ранее мы уже встречали простое число
            if i - last == 2: # проверяем, что разность между двумя простыми числами равна 2
                ans += 1
            last = i
print(ans)

Ответ: 7031

Ошибка.
Попробуйте повторить позже

Задача 18#30241

Числа-близнецы — это такие простые числа, которые отличаются друг от друга на $2$ . Найдите все пары чисел-близнецов в диапазоне [17 000 000; 23 000 000], сумма которых будет кратна $50000$ . В ответ запишите найденные пары, числа в которых записаны по возрастанию.

Показать ответ и решение

Неэффективное решение

def prime(x):# функция для проверки, что число - простое
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
ans = 0
flag = True
for i in range(17000000, 23000000+1):
    if prime(i):
        if flag:
            last = i
            flag = False
        else:
            if i - last == 2:
                if (last + i) % 50000 == 0:
                    print(last, i)
            last = i

Эффективное решение

def prime(x):# функция для проверки, что число - простое
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

# Мы знаем, что в ответе x и x + 2 — простые числа с
# суммой кратной 50000, то есть x + x + 2 = 50000t
# то есть x = 25000t - 1.
# t можно оценить как правая граница // 25000
for i in range(1, 23*10**6 // 25000):
    x = 25000*i - 1
    if 17*10**6 <= x <= 23*10**6 - 2:
        if prime(x) and prime(x + 2):
            print(x, x + 2)

Ответ: 22049999 22050001 22424999 22425001 22574999 22575001 22949999 22950001

Ошибка.
Попробуйте повторить позже

Задача 19#32438

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[56846;59033]$ , простые числа. Программа должна вывести количество таких чисел.

Показать ответ и решение

def is_prime(n): # функция для проверки, что число - простое
    if n == 1: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
k = 0
for x in range(56846, 59034):
    if is_prime(x):
        k += 1
print(k)

Ответ: 204

Ошибка.
Попробуйте повторить позже

Задача 20#54978

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [4301614; 4301717], простые числа. В качестве ответа выводите сначала порядковый номер найденного числа, затем через пробел само число. Далее через пробел повторите это для следующего найденного числа. То есть формат ответа: номер1 число1 номер2 число2 ...

Показать ответ и решение

def is_prime(number): # функция для проверки, что число - простое
    if number == 1: return False
    for div in range(2, int(number ** 0.5) + 1):
        if number % div == 0:
            return False
    return True


for i in range(4301614, 4301717 + 1):
    if is_prime(i):
        print(i - 4301614 + 1, i, end=’ ’)

Ответ: 10 4301623 56 4301669 86 4301699 88 4301701 94 4301707

25.02 Особые числа (простые, фибоначи, факториал, палиндромы)