Вычисление последовательности Хэмминга в C++ (последовательность чисел, которая имеет только 2, 3 и 5 в качестве делителей)

Question

Возможный дубликат:
Генерация последовательности с использованием только простых чисел 2, 3 и 5, а затем отображение n-го члена (C++)

Я всегда думал об этом, и я просто не могу понять это. Мне нужно решить следующую проблему:

Создайте следующую последовательность и отобразите n-й член в последовательности

2,3,4,5,6,8,9,10,12,15 и т. Д...... В последовательности есть только простые числа 2,3,5

Мне нужно использовать базовый C++, такой как while, for, if и т. Д. Ничего особенного. Я не могу использовать массивы просто потому, что я еще мало о них знаю, и я хочу понять код решения.

Я не прошу полного решения, но я прошу руководство, чтобы пройти через это... пожалуйста.

Моя проблема в том, что я не могу понять, как проверить, делится ли число, если число в последовательности делится на любые другие простые числа, кроме 2, 3 и 5.

Также предположим, что я проверяю число следующим образом:

for(int i=2; i<n; i++){
    if(i%2==0){
        cout<<i<<", ";
    }else if(i%3==0){
        cout<<i<<", ";
    }else if(i%5==0){
        cout<<i<<", ";
    }

Он не работает просто из-за того, что он будет производить числа, такие как 14, которые могут быть разделены на простое число 7. Поэтому мне нужно выяснить, как обеспечить, чтобы эта последовательность делилась только на 2, 3 и 5..... Я нашел много материалов в Интернете с решениями проблемы, но решения, которые у них есть, слишком развиты, и я не могу их использовать (также большинство из них на других языках... нет C++). Я уверен, что есть более простой способ.

Answer 1

Проблема с вашим кодом заключается в том, что вы просто проверяете один из основных факторов, а не все.

Возьмем для примера 14. Ваш код проверяет, является ли 2,3 или 5 фактором 14, что не совсем то, что вам нужно. Действительно, вы обнаружите, что 2 - это коэффициент 14, но другой фактор, как вы сказали, равен 7. Чего вам не хватает, так это дальнейшей проверки, имеет ли 7 только факторы 2,3 и 5 (что не так). Что вам нужно сделать, это устранить все факторы 2,3 и 5 и посмотреть, что осталось.

Давайте возьмем два примера: 60 ​​и 42

Для 60

Начните с факторов 2

• 60% 2 = 0, так что теперь проверьте 60/2 = 30.
• 30% 2 = 0, так что теперь проверьте 30/2 = 15.
• 15% 2 = 1, так что нет больше факторов 2.

Продолжайте с факторами 3

• 15% 3 = 0, так что теперь проверьте 15/3 = 5.
• 5% 3 = 2, так что больше не будет факторов 3.

Закончите с факторами 5

• 5% 5 = 0, так что теперь проверьте 5/5 = 1
• 1% 5 = 1, так что больше не будет факторов 5.

Мы заканчиваем с 1, так что это число является частью последовательности.

Для 42

Опять начнем с факторов 2

• 42% 2 = 0, так что теперь проверьте 42/2 = 21.
• 21% 2 = 1, так что нет больше факторов 2.

Продолжайте с факторами 3

• 21% 3 = 0, так что теперь проверьте 21/3 = 7.
• 7% 3 = 1, так что нет больше факторов 3.

Закончите с факторами 5

• 7% 5 = 2, так что нет больше факторов 5.

В итоге получается 7 (что-то отличное от 1), поэтому это число НЕ является частью последовательности.

Таким образом, в вашей реализации вы, вероятно, должны использовать 3 цикла while в цикле for, чтобы отразить это.

Answer 2

Сохраните следующее значение i во временной переменной, а затем разделите его на 2 столько, сколько сможете (например, до тех пор, пока i%2 == 0). Затем разделите на 3 как можно дольше. Потом на 5. А потом проверь, что осталось.

Answer 3

Как насчет этого?

bool try_hamming(int n)
{
    while(n%2 == 0)
    {
        n = n/2;
    }
    while(n%3 == 0)
    {
        n = n/3;
    }
    while(n%5 == 0)
    {
        n = n/5;
    }
    return n==1;
}

Это должно вернуть true, когда n - число Хэмминга, и false - в противном случае. Так что основная функция может выглядеть примерно так

 #include<iostream>
 using namespace std;
 main()
 {
      for(int i=2;i<100;++i)
      {
          if(try_hamming(i) )
          cout<< i <<",";
       }
      cout<<end;
  }

это должно распечатать все числа Хемминга меньше 100