Написание программы по теме "Обработка целых данных"

@Timurscor · Регистрация: 28.02.2022

Author24 — интернет-сервис помощи студентам

Для натуральных чисел, не превосходящих заданного числа N, найти все простые числа, сумма цифр которых равна М.

@gunslinger · 29.05.2022, 20:43

Есть ограничение на максимальное значение N?

@Timurscor · 29.05.2022, 20:44 **[ТС]**

Ограничений нет.

@gunslinger · 29.05.2022, 21:29

Взял код проверки на простоту отсюда: Разработайте программу, находящую все простые числа в диапазоне от 0x80000001 до 0xFFFFFFFF.

C++

bool isPrime(unsigned long long x)
{
  if (x == 2)
    return true;
  if (x < 3 || (x & 1) == 0)
    return false;
 
  unsigned long long i, ii;
  for (i = 3, ii = 9; ii <= x; ii += (i << 2) + 4, ++++i)
    if (x % i == 0)
      return false;
 
  return true;
}

Основной код:

C++

  unsigned long long N = 10000000, M = 13, i, sum, tmp;
  for (i = 2; i <= N; i++)
  {
    sum = 0;
    tmp = i;
    do
    {
      sum += tmp % 10;
      tmp /= 10;
    } while(tmp);
 
    if (sum == M && isPrime(i))
      // выводим i
  }

Только при больших N будет работать долго и N не может быть больше 0xFFFFFFFF (64 бита).
Плюс не при всех M будет что-то выводиться.
Результат при значениях параметров из кода выше (получается 2727 чисел):

Код

@Timurscor 0 / 0 / 0 Регистрация: 28.02.2022 Сообщений: 4
		1
	Написание программы по теме "Обработка целых данных" 29.05.2022, 20:02. Показов 541. Ответов 3 Метки натуральные числа, простые числа, сумма цифр (Все метки) Для натуральных чисел, не превосходящих заданного числа N, найти все простые числа, сумма цифр которых равна М. 0

@gunslinger случайный прохожий 2919 / 1936 / 606 Регистрация: 20.07.2013 Сообщений: 5,132
	29.05.2022, 20:43	2
	Есть ограничение на максимальное значение N? 0

@Timurscor 0 / 0 / 0 Регистрация: 28.02.2022 Сообщений: 4
	29.05.2022, 20:44 [ТС]	3
	Ограничений нет. 0

	29.05.2022, 21:29

Опции темы

Написание программы по теме "Обработка целых данных"

Решение