Простые числа —Каталог задач по ЕГЭ - Информатика

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

Задача 1#32438

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

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

def is_prime(n):
    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

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

Задача 2#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

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

Задача 3#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
flag = True
for i in range(500000, 1500000+1):
    if prime(i):
        if flag:
            last = i
            flag = False
        else:
            if i - last == 2:
                ans += 1
            last = i
print(ans)

Ответ: 7031

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

Задача 4#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

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

Задача 5#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

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

Задача 6#30209

Найти минимальное число, большее $156239$ , которое имеет ровно $60$ делителей, из которых ровно $4$ – простые. В ответе запишите все простые делители найденного числа в порядке возрастания.

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

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 okay(n):
    k, k_pr = 0, 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            k += 1
            if prime(i):
                k_pr += 1
            if n // i != i:
                k += 1
                if prime(n // i):
                    k_pr += 1
    if k == 60 and k_pr == 4:
        return True
    return False

def prime_divs(n):
    a = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if prime(i):
                a.append(i)
            if n // i != i and prime(n // i):
                a.append(n // i)
    a.sort()
    return a

ans = 0
for i in range(156239, 10000000):
    if okay(i):
        ans = i
        break
print(*prime_divs(ans))

Ответ: 2 5 17 23

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

Задача 7#30208

Назовем число добрым, если среди его делителей есть хотя бы три квадрата простых чисел. Найти 5 минимальных добрых чисел, больших $21317$ . В ответе запишите найденные числа через пробел в порядке возрастания.

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

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 okay(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if int(i ** 0.5) == i ** 0.5 and prime(i ** 0.5):
                k += 1
            if n // i != i:
                x = n // i
                if int(x ** 0.5) == x ** 0.5 and prime(x ** 0.5):
                    k += 1
        if k >= 3:
            return True
    return False

counter = 0
for i in range(21317, 100000000):
    if okay(i):
        print(i, end=’ ’)
        counter += 1
    if counter == 5:
        break

Ответ: 21600 21780 22050 22500 22932

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

Задача 8#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

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

Задача 9#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

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

Задача 10#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

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

Задача 11#30198

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

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

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 okay(n):
    k = 0  # счетчик простых делителей, оканчивающихся на 7
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if prime(i) and (i % 10 == 7):
                k += 1
            if n // i != i:
                if prime(n // i) and ((n // i) % 10 == 7):
                    k += 1
        if k >= 2:
            return True
    return False

def count_div(n):
    k = 2
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            k += 1
            if n // i != i:
                k += 1
    return k

counter, maxim = 0, 0
for i in range(654321, 712346):
    if okay(i):
        counter += 1
        if count_div(i) > maxim:
            maxim = count_div(i)
print(counter, maxim)

Ответ: 5055 192

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

Задача 12#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

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

Задача 13#30192

Проверить число $41203$ на простоту. Вывести «Prime», если число простое, иначе вывести «Not prime».

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

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

if prime(41203):
    print(’Prime’)
else:
    print(’Not prime’)

Ответ: Prime

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

Задача 14#29460

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

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

def is_prime(n):
    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

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

Задача 15#28547

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

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

def is_prime(n):
    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

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

Задача 16#27893

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

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

def divs(n):
    div = []    # Массив делителей
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n//i:
                div.append(n//i)
    return div

def is_prime(n):
    if n == 2:  # Для ускорения кода обработаем сразу четность
        return True
    elif n % 2 == 0:
        return False
    else:
        for j in range(3, int(n**0.5) + 1, 2):
            if n % j == 0:
                return False
    return True

def count_prime_divs(n):    # Просто счетчик простых делителей
    counter = 0
    for i in divs(n):
        if is_prime(i):
            counter += 1
    return counter

a = 52112  # Задаю границы цикла
b = 623122
ans = 0   # Будущий ответ
for i in range(a, b + 1):
    if count_prime_divs(i) == 3:
        ans += 1
print(ans)

$\text{[math]}$

Ответ: 218197

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

Задача 17#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

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

Задача 18#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

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

Задача 19#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

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

Задача 20#22666

Числа-близнецы $−$ это такие простые числа, которые отличаются друг от друга на 2. Найдите все пары чисел-близнецов в диапазоне [2 500 000; 3 500 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(2500000, 3500000+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

Ответ: 3149999 3150001