@jinxonik / UniLecs #151

SmithNumbers.cpp

#include <iostream>
#include <ctime>

using std::cout;
using std::ldiv;
using std::ldiv_t;

using num_t = long int;  // тип проверяемого числа
using sum_t = int;       // тип суммы цифр

// Класс нахождения чисел Смита
class SmithNumbers
{
  // Вычислить сумму цифр числа n
  static sum_t dig_sum(num_t n);
public:
  // Проверить - является ли число n числом Смита
  static bool check(num_t n);
  // Найти len идущих подряд чисел Смита, начиная с числа n и вернуть первое из них
  // Максимальное число в последовательности не должно превышать n_max
  // Если число не найдено, возвращается 0
  static num_t sequence(size_t len, num_t n, num_t n_max);
};

// Вычислить сумму цифр числа n
sum_t SmithNumbers::dig_sum(num_t n)
{
  if (n < 10) { return n; }
  sum_t sum = 0;  // сумма

  while (n > 0) {
    sum += n % 10;  // добавляем остаток
    n /= 10;
  }

  return sum;  // возвращаем сумму
}

// Проверить - является ли число n числом Смита
bool SmithNumbers::check(num_t n)
{
  if (n < 4) { return false; }  // до 4 чисел Смита нет

  num_t q = n;     // делаем копию исходного числа
  sum_t fsum = 0;  // сумма цифр сомножителей
  // Сомножитель 2
  while (!(q&1)) {  // пока число чётное
    fsum += 2;  // добавляем 2 к сумме
    q >>= 1;    // делим q пополам
  }
  // Сомножитель 3 (при оптимизации использование % и / будет быстрее, чем ldiv)
  while (q % 3 == 0) {
    fsum += 3;  // добавляем сумму цифр сомножителя
    q /= 3;
  }
  // Сомножители 5, 7, 11, 13, 17, 19, 23...
  ldiv_t d;      // частное и остаток
  // i - проверяемый сомножитель, add - приращение (add ^= 6 - чередование 2 и 4)
  for (num_t fac = 5, add = 2; fac*fac <= q; fac += add, add ^= 6) {
    while (d = ldiv(q, fac), d.rem == 0) {  // вычисляем частное и остаток от деления на fac...
      // ...и продолжаем, если остаток == 0
      fsum += dig_sum(fac);  // добавляем сумму цифр сомножителя
      q = d.quot;  // q /= fac;
    }
  }
  // Остаток
  if (q > 1 && fsum > 0) {
    fsum += dig_sum(q);  // добавляем число к сумме, если число не простое
  }

  return (fsum == dig_sum(n));  // возвращаем результат сравнения сумм
}

// Найти len идущих подряд чисел Смита, начиная с числа n и вернуть первое из них
// Максимальное число в последовательности не должно превышать n_max
// Если число не найдено, возвращается 0
num_t SmithNumbers::sequence(size_t len, num_t n, num_t n_max)
{
  if (len < 1) { return 0; }  // возвращаем 0 при заданной длине последовательности < 1
  if (n < 0) { n = 4; }  // начинаем минимум с 4

  for (size_t cur = 0; n-1 < n_max; ++n) {  // n <= n_max не сработает при n_max = LONG_MAX
    if (check(n)) {  // проверяем число
      if (++cur == len) {  // увеличиваем длину и сравниваем с нужной
        return n - len + 1;  // возвращаем результат
      }
    } else { cur = 0; }  // обнуляем длину, если это не число Смита
  }

  return 0;  // чисел Смита длиной len между n и n_max нет
}

////////////////////////////////////////////////////////////////////////////////////////////////////

// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t start_time;
public:
  // Запустить таймер
  void start()
  {
    start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};

////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
  const size_t SEQ_LEN   = 4;           // минимальное кол-во идущих подряд чисел Смита
  const num_t  N_START   = 1;           // начальное число
  const num_t  N_MAX     = 10'000'000;  // максимальное число
  const int    SEQ_COUNT = 10;          // кол-во искомых последовательностей

  cout << "Calculating " << SEQ_COUNT << " sequences by " << SEQ_LEN << " Smith numbers in range " << N_START << ".." << N_MAX << " ...\n";

  TimeMeasure tm;
  tm.start();

  num_t n = N_START;    // стартовое значение
  for (int i = 0; i < SEQ_COUNT && n > 0; ++i, ++n) {  // n > 0 на случай переполнения
    n = SmithNumbers::sequence(SEQ_LEN, n, N_MAX);  // находим следующую последовательность
    // Проверка результата
    if (n == 0) {
      cout << "Not enought numbers between " << N_START << " and " << N_MAX << " !!!\n";
      break;  // если чисел нет, выходим из цикла
    }
    // Выводим числа последовательности
    for (int j = 0; j < SEQ_LEN; ++j) {
      if (j > 0) { cout << ", "; }
      cout << n + j;
    }
    cout << "\n";
  }

  tm.stop_and_show();

  return 0;
}

SmithNumbers1.cpp

// Чуть более быстрая (но и чуть более громоздкая) версия.
// Добавлены приращения (add) в виде таблицы. Деление на 2, 3 и 5 сделано вручную.
// Таким образом, в цикле for метода check перебираются числа, не делящиеся на 2, 3 и 5.

#include <iostream>
#include <ctime>

using std::cout;
using std::ldiv;
using std::ldiv_t;

using num_t = long int;  // тип проверяемого числа
using sum_t = int;       // тип суммы цифр

// Класс нахождения чисел Смита
class SmithNumbers
{
  // Вычислить сумму цифр числа n
  static sum_t dig_sum(num_t n);
public:
  // Проверить - является ли число n числом Смита
  static bool check(num_t n);
  // Найти len идущих подряд чисел Смита, начиная с числа n и вернуть первое из них
  // Максимальное число в последовательности не должно превышать n_max
  // Если число не найдено, возвращается 0
  static num_t sequence(size_t len, num_t n, num_t n_max);
};

// Вычислить сумму цифр числа n
sum_t SmithNumbers::dig_sum(num_t n)
{
  if (n < 10) { return n; }
  sum_t sum = 0;  // сумма

  while (n > 0) {
    sum += n % 10;  // добавляем остаток
    n /= 10;
  }

  return sum;  // возвращаем сумму
}

// Проверить - является ли число n числом Смита
bool SmithNumbers::check(num_t n)
{
  if (n < 4) { return false; }  // до 4 чисел Смита нет

  num_t q = n;     // делаем копию исходного числа
  sum_t fsum = 0;  // сумма цифр сомножителей
  // Сомножитель 2
  while (!(q&1)) {  // пока число чётное
    fsum += 2;  // добавляем 2 к сумме
    q >>= 1;    // делим q пополам
  }
  // Сомножитель 3 (при оптимизации использование % и / будет быстрее, чем ldiv)
  while (q % 3 == 0) {
    fsum += 3;  // добавляем сумму цифр сомножителя
    q /= 3;
  }
  // Сомножитель 5 (при оптимизации использование % и / будет быстрее, чем ldiv)
  while (q % 5 == 0) {
    fsum += 5;  // добавляем сумму цифр сомножителя
    q /= 5;
  }
  // Сомножители 7, 11, 13, 17, 19, 23, 29, 31, 37...
  ldiv_t d;  // частное и остаток
  static const num_t add[] = {4, 2, 4, 2, 4, 6, 2, 6};
  // i - проверяемый сомножитель, add - приращение, ai - индекс в массиве add
  for (num_t fac = 7, ai = 0; fac*fac <= q; fac += add[ai], ai = ai+1 & 7) {
    while (d = ldiv(q, fac), d.rem == 0) {  // вычисляем частное и остаток от деления на fac...
      // ...и продолжаем, если остаток == 0
      fsum += dig_sum(fac);  // добавляем сумму цифр сомножителя
      q = d.quot;  // q /= fac;
    }
  }
  // Остаток
  if (q > 1 && fsum > 0) {
    fsum += dig_sum(q);  // добавляем число к сумме, если число не простое
  }

  return (fsum == dig_sum(n));  // возвращаем результат сравнения сумм
}

// Найти len идущих подряд чисел Смита, начиная с числа n и вернуть первое из них
// Максимальное число в последовательности не должно превышать n_max
// Если число не найдено, возвращается 0
num_t SmithNumbers::sequence(size_t len, num_t n, num_t n_max)
{
  if (len < 1) { return 0; }  // возвращаем 0 при заданной длине последовательности < 1
  if (n < 0) { n = 4; }  // начинаем минимум с 4

  for (size_t cur = 0; n-1 < n_max; ++n) {  // n <= n_max не сработает при n_max = LONG_MAX
    if (check(n)) {  // проверяем число
      if (++cur == len) {  // увеличиваем длину и сравниваем с нужной
        return n - len + 1;  // возвращаем результат
      }
    } else { cur = 0; }  // обнуляем длину, если это не число Смита
  }

  return 0;  // чисел Смита длиной len между n и n_max нет
}

////////////////////////////////////////////////////////////////////////////////////////////////////

// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t start_time;
public:
  // Запустить таймер
  void start()
  {
    start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};

////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
  const size_t SEQ_LEN   = 4;           // минимальное кол-во идущих подряд чисел Смита
  const num_t  N_START   = 1;           // начальное число
  const num_t  N_MAX     = 10'000'000;  // максимальное число
  const int    SEQ_COUNT = 10;          // кол-во искомых последовательностей

  cout << "Calculating " << SEQ_COUNT << " sequences by " << SEQ_LEN << " Smith numbers in range " << N_START << ".." << N_MAX << " ...\n";

  TimeMeasure tm;
  tm.start();

  num_t n = N_START;    // стартовое значение
  for (int i = 0; i < SEQ_COUNT && n > 0; ++i, ++n) {  // n > 0 на случай переполнения
    n = SmithNumbers::sequence(SEQ_LEN, n, N_MAX);  // находим следующую последовательность
    // Проверка результата
    if (n == 0) {
      cout << "Not enought numbers between " << N_START << " and " << N_MAX << " !!!\n";
      break;  // если чисел нет, выходим из цикла
    }
    // Выводим числа последовательности
    for (int j = 0; j < SEQ_LEN; ++j) {
      if (j > 0) { cout << ", "; }
      cout << n + j;
    }
    cout << "\n";
  }

  tm.stop_and_show();

  return 0;
}