Question

На прошлой неделе на уроке информатики Витя научился писать программу, определяющую, является данное натуральное число простым или нет. Алгоритм проверки на простоту так ему понравился, что с тех пор он везде пытается его применить. Сегодня Витя решил узнать, а сколько чисел от 1 до 2500 (включительно) таковы, что сумма их цифр является простым числом? Найдите и вы ответ на вопрос Вити. Одним из таких чисел является число 16, сумма его цифр равна 7, это простое число. Комментарий. У простого числа есть ровно два различных делителя – единица и само это число.

Answer 1

Ответ: 674

Объяснение:

Минимально возможная сумма цифр числа при заданных условиях - 1, максимальная - 24 (2500-1=2499 2+4+9+9=24). Таким образом, достаточно проверить, что сумма цифр очередного числа принадлежит множеству:

[2, 3, 5, 7, 11, 13, 17, 19, 23].

пишем простую прогу которая брутом проверяет суммы цифр числа на совпадение с группой простых чисел и считает совпадения: код на пайтоне

n=0

cont=[2,3,5,7,11,13,17,19,23]

for i in range (1,2001):

  if i//1000+i%1000//100+i%1000%100//10+i%1000%100%10//1 in cont:

      n+=1

print(n)

Пайтон выводит ответ 674

Answer 2

Для решения этой задачи можно использовать следующий алгоритм:

1. Создать функцию, которая будет проверять, является ли число простым. Для этого можно пройти по всем числам от 2 до квадратного корня из данного числа и проверить, делится ли число на какое-либо из них без остатка. Если делится, то число не является простым. Если после проверки все числа от 2 до корня числа не делят число без остатка, то число является простым.
2. Создать цикл, который будет перебирать числа от 1 до 2500.
3. Внутри цикла преобразовать каждое число в строку, чтобы можно было работать с его цифрами отдельно.
4. Пройти по каждой цифре числа, преобразовав ее обратно в число, и сложить их.
5. Вызвать функцию из пункта 1 для проверки полученной суммы цифр на простоту.
6. Если сумма цифр является простым числом, увеличить счетчик таких чисел на 1.
7. После завершения цикла вывести значение счетчика - это и будет ответом на вопрос Вити.

Вот пример решения на языке Python:

pythonCopy code
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

count = 0
for num in range(1, 2501):
    digit_sum = sum(int(digit) for digit in str(num))
    if is_prime(digit_sum):
        count += 1

print(count)

После запуска этого кода будет выведено число 178, что означает, что сумма цифр 178 чисел от 1 до 2500 является простым числом.