divisble by prime numbers only sequence
I need help with a strange homework question
"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."
any help is appreciated!
"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."
any help is appreciated!
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.
I'm still having a little difficulty coding it numbers like 14 are divisible by the prime number 2 but its other factor 7 is not a prime number
Last edited on
Missed the "only". If you divide the number by 2 as many times as you can, then by 3 and last by 5, you should end up with 1 or something bigger.
for (int num=1; num/2 || num/3 || num/5 == 1 || 2 || 3 || 5; ++num)would something like this work?
and how do I get it just to print out the 1501st term?
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.
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.
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.
|
|
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.
What I have so far?
|
|
Well, there's a bit of a problem there.
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.
|
|
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 = 2a 3b 5c
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)
The sequence consist of number in the form n = 2a 3b 5c
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)
Last edited on
| the real issue here is getting something which will run in a reasonably short timescale. |
$ g++ -O3 prettymuchanoob.cpp $ time ./a.out 1501-th number is ######### real 0m15.346s user 0m15.325s sys 0m0.011s $ |
Topic archived. No new replies allowed.