"numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 numbers. By convention, 1 is included.
Write a program to find and print the 1501'st number.
There is no input to this program. Output should consist of a single line as shown below,
with <number> replaced by the number computed."
Simple. Go through numbers. If it is divisible by any of the three, then increase the counter. When the counter reaches 1501, print the current number and quit.
Well, the real issue here is getting something which will run in a reasonably short timescale.
It's straightforward enough to do it by a brute-force method. Start with an ordinary while loop which tests each integer in turn starting with 2, to see whether its only factors are any of 2, 3 or 5.
How to test the factors. Let's say you have the number 8, you want to know if its only factor is 2.
1 2 3 4 5 6 7
int num = 8;
while (num %2 == 0)
num /= 2;
if (num == 1)
cout << "success";
You just need to extend this to also cover factors of 3 and 5.
Test this out, but start small, just try to find the first 10 or 20 numbers in the series to begin with, as it can run quite slowly with the larger values.
Also, don't forget that the first number in the sequence is 1, even though it doesn't have any of the others as its factors.
Well, I'm trying to help, but if I say very much more, I will have done the entire thing for you. How about you write the program as best you can, and then come back with questions. I always find with stuff like this, I never really understand it till I start to get pretty deep into the middle of it.
Yes, that's the idea. But its easy enough to test this for yourself. Try some easy numbers like 12 and 15, as well as some failed ones like 14 or 22. Once you're satisfied with testing an individual number, you can move on to trying to put it inside a loop.
int x = 1, y = 2, z = 3, i=5;
for(x = 1; x <=1501; ++x)
{
while(x % y == 0){
x /= y;
}
while(x % z == 0){
x/=z;
}
while(x % i == 0){
x/=i;
}
if (x == 1)
cout << x;
That can only ever print the number 1.
And worse, because x is used to control the for loop, the loop will never finish, as x keeps being set back to the starting value.
So how to solve that? Well you could introduce a temporary variable, make a copy of x and use the copy for the testing purposes.
> the real issue here is getting something which will run in a reasonably short timescale.
The sequence consist of number in the form n = 2^{a} 3^{b} 5^{c}
So you can simply generate numbers from the sequence, sort them and pick up the 1501th element.
The problem would be the limits for `a', `b' and `c' in order to guarantee that our container holds the exact sequence until the 1501 position, (no holes)