Calculating Hamming Sequence in C++ (a sequence of numbers that has only 2, 3, and 5 as dividers)

Question

Possible Duplicate:
Generating a sequence using prime numbers 2, 3, and 5 only, and then displaying an nth term (C++)

I've been brainstorming over this forever, and I just can't figure this out. I need to solve the following problem:

Generate the following sequence and display the nth term in the sequence

2,3,4,5,6,8,9,10,12,15, etc..... Sequence only has Prime numbers 2,3,5

I need to use basic C++, such as while, for, if, etc. Nothing fancy. I can't use arrays simply because I don't know much about them yet, and I want to understand the code for the solution.

I'm not asking for a complete solution, but I am asking for guidance to get through this... please.

My problem is that I can't figure out how to check if the number if the number in the sequence is divisible by any other prime numbers other than 2, 3, and 5.

Also let's say I'm checking the number like this:

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<<", ";
    }

It doesn't work simply due to the fact that it'll produce numbers such as 14, which can be divided by prime number 7. So I need to figure out how to ensure that that sequence is only divisible by 2, 3, and 5..... I've found lots of material online with solutions for the problem, but the solutions they have are far too advance, and I can't use them (also most of them are in other languages... not C++). I'm sure there's a simpler way.

Answer 1

The problem with your code is that you just check one of the prime factors, not all of them.

Take your example of 14. Your code only checks if 2,3 or 5 is a factor of 14, which is not exactly what you need. Indeed, you find that 2 is a factor of 14, but the other factor is 7, as you said. What you are missing is to further check if 7 has as only factors 2,3 and 5 (which is not the case). What you need to do is to eliminate all the factors 2,3 and 5 and see what is remaining.

Let's take two examples: 60 and 42

For 60

Start with factors 2

• 60 % 2 = 0, so now check 60 / 2 = 30.
• 30 % 2 = 0, so now check 30 / 2 = 15.
• 15 % 2 = 1, so no more factors of 2.

Go on with factors 3

• 15 % 3 = 0, so now check 15 / 3 = 5.
• 5 % 3 = 2, so no more factors of 3.

Finish with factors 5

• 5 % 5 = 0, so now check 5 / 5 = 1
• 1 % 5 = 1, so no more factors of 5.

We end up with 1, so this number is part of the sequence.

For 42

Again, start with factors 2

• 42 % 2 = 0, so now check 42 / 2 = 21.
• 21 % 2 = 1, so no more factors of 2.

Go on with factors 3

• 21 % 3 = 0, so now check 21 / 3 = 7.
• 7 % 3 = 1, so no more factors of 3.

Finish with factors 5

• 7 % 5 = 2, so no more factors of 5.

We end up with 7 (something different from 1), so this number is NOT part of the sequence.

So in your implementation, you should probably nest 3 while loops in your for loop to reflect this reasoning.