Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > полнократные числа

Автор: 1101s 12.9.2018, 22:08

Здравствуйте, бьюсь над задачей, и никак не доходит, как адекватно располагать loops и if-else. Задачка такая: нужно написать программу, которая указывает полнократное ли n, (2 <= n <= 2000000000). То есть число, корень которого является свободным от квадратов. Например, 21 - свободное от квадратов число, 21^2 = 441, значит 441 - полнократное. В задаче нельзя использовать никакие математические функции, по сути только петли и if-else. Народ, помогите плес.
****

Автор: feodorv 13.9.2018, 12:32

Если я правильно понял, то не полные квадраты (например, 2 или 3) не являются полнократными числами?

Число полных квадратов, меньших или равных 2*10^9, около 45000. Так что всё можно предрасчитать заранее, в дальнейшем пользуясь лишь бинарным поиском. А можно всё сделать в одном месте:

Код


bool isFullFoldNumber( int n )
{
  int sq, d;
  for( sq = 1; sq * sq < n; ++sq) /* nothing */;
  if( sq * sq != n ) return false;
  for( d = 2; d * d <= sq; ++d)
    if( sq % (d * d) == 0 ) return false;
  return true;
}

Другой подход - факторизация числа с последующими проверками. Приведённый код не тестировал. Успехов!

Автор: okalitut 7.12.2018, 13:20

Цитата(feodorv @ 13.9.2018, 12:32)

Код


bool isFullFoldNumber( int n )
{
  int sq, d;
  for( sq = 1; sq * sq < n; ++sq) /* nothing */;
  if( sq * sq != n ) return false;
  for( d = 2; d * d <= sq; ++d)
    if( sq % (d * d) == 0 ) return false;
  return true;
}

Другой подход - факторизация числа с последующими проверками. Приведённый код не тестировал. Успехов!

Была похожая задача, и в решении очень помог ваш ответ! Спасибо!