1. ## Help with this please

Ok so i have been coding this problem.The problem ">
For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of `homble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a homble number.
Your job is to find the Nth homble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.
Input format
Line 1: Two space separated integers: K and N, 1 <= K <=100 and 1 <= N <= 100,000.
Line 2: K space separated positive integers that comprise the set S.
<<
The program works fine up to a point.but when the numbers start to get bigg it crashes with no output.These are the tests i run on it. Test 4 fails miserably. Can someone help me out please. Thanks in advance.

Sample test data and answers supposed to generate:
Test 1
5 50
2 3 11 13 17

Ans: 176
---------------------------------
Test 2
6 1000
2 3 5 11 17 23

Ans: 48114
-------------------------------
Test 3
15 10000
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Ans: 106856
------------------------------
Test 4
7 28888
2 3 5 11 17 23 31

Ans: 905084928

[code]

2. Code:
```long findHumbles(){//finds humbles and returns Nth humble number
int i=2,j=0;```
If you needed to use long elsewhere why are these two variables not long?

Tim S.

3. Originally Posted by stahta01
Code:
```long findHumbles(){//finds humbles and returns Nth humble number
int i=2,j=0;```
If you needed to use long elsewhere why are these two variables not long?

Tim S.
yes you are right, must have accidentally left it that way while im troubleshooting. I am passing in a long int into my humble test so it must be a long. doesnt affect the situation though :S

4. Global variables are horrible, dirty, nasty things. Read why here: Global Variables Are Bad. You should make them locals and pass them around, so your code is easier to debug. Also, try a better indentation style, that will make it easier to understand what pieces of code belong in what blocks.

Now, as for your problem, this is speculative because I didn't feel like waiting for my computer to run billions upon billions of calculations. I think the reason your program crashes is that you are overflowing i, so it wraps around to a negative number, then, when you access S[i], you cause a seg fault (negative indexes are bad, especially really big ones). As for why you're overflowing, I think your humbleTest function isn't quite correct. If I understand the algorithm correctly, it should look something like this:
Code:
```for each element in S
while num % S[i] == 0  // while loop accounts for numbers that are comprised of, e.g. p1p1
num /= S[i]

if num == 1  // if there are no prime factors left (i.e. all num's prime factors are in S)
return humble number```

5. Originally Posted by anduril462
Global variables are horrible, dirty, nasty things. Read why here: Global Variables Are Bad. You should make them locals and pass them around, so your code is easier to debug. Also, try a better indentation style, that will make it easier to understand what pieces of code belong in what blocks.

Now, as for your problem, this is speculative because I didn't feel like waiting for my computer to run billions upon billions of calculations. I think the reason your program crashes is that you are overflowing i, so it wraps around to a negative number, then, when you access S[i], you cause a seg fault (negative indexes are bad, especially really big ones). As for why you're overflowing, I think your humbleTest function isn't quite correct. If I understand the algorithm correctly, it should look something like this:
Code:
```for each element in S
while num % S[i] == 0  // while loop accounts for numbers that are comprised of, e.g. p1p1
num /= S[i]

if num == 1  // if there are no prime factors left (i.e. all num's prime factors are in S)
return humble number```
ok my program did look messy cleaned it up a bit. But im not sure i understand how that algo will find the 'kth' number in the sequence. I think the problem is the findhumble function is incapable of storing large numbers since the tests with smaller numbers work and thats the function that is returning..i most likely am wrong .please clarify your suggestion thanks.

6. Reread my post. I said that that algo is for your humbleTest function, which does not find the kth number in the sequence. It simply checks if a given number is a valid humble number for your set of primes, S. Even your humbleTest function didn't find the kth number itself. It needed the help of findHumbles, and so does my algo. It's a drop-in replacement for your humbleTest algo. The function signature doesn't even have to change.

The big reason mine works and yours doesn't is the while loop inside the for loop. You only divide by each number in S once (you use an if). That means you skip lots of valid humble numbers. For example, if S = {2, 3, 5} and num= 900 would be a valid humble number because it's 2 * 2 * 3 * 3 * 5 * 5. You would need to divide num by 2 twice, 3 twice and 5 twice to bring it down to 1 and determine that it's a valid humble number. Your program would just divide by 2, then 3, then 5, giving you 30, and failing the test.

I just implemented it and it worked like a charm for all four tests. Tests 1-3 took less than a second. Test 4 took 95 seconds.

EDIT: Your old code is gone. Post new code if you're still having trouble.

7. Originally Posted by anduril462
Reread my post. I said that that algo is for your humbleTest function, which does not find the kth number in the sequence. It simply checks if a given number is a valid humble number for your set of primes, S. Even your humbleTest function didn't find the kth number itself. It needed the help of findHumbles, and so does my algo. It's a drop-in replacement for your humbleTest algo. The function signature doesn't even have to change.

The big reason mine works and yours doesn't is the while loop inside the for loop. You only divide by each number in S once (you use an if). That means you skip lots of valid humble numbers. For example, if S = {2, 3, 5} and num= 900 would be a valid humble number because it's 2 * 2 * 3 * 3 * 5 * 5. You would need to divide num by 2 twice, 3 twice and 5 twice to bring it down to 1 and determine that it's a valid humble number. Your program would just divide by 2, then 3, then 5, giving you 30, and failing the test.

I just implemented it and it worked like a charm for all four tests. Tests 1-3 took less than a second. Test 4 took 95 seconds.

EDIT: Your old code is gone. Post new code if you're still having trouble.

ok here is the implementation what you said.It crashes though

Code:
```int humbleTest(long num){//test if a number is humble or not
int i;
long n;
n = num;

for(i=0;i<length;i++){
while(num % S[i]==0) {
num= num/ S[i];
}
}
if(num == 1 || num < 0) return n;
}```

8. Code:
`if((i==0) &&(num =initNum)) break;`
= is assignment.
== is for equality testing.

Quzah.

9. should have == there instead of =

10. Originally Posted by anduril462
Code:
```for each element in S
while num % S[i] == 0  // while loop accounts for numbers that are comprised of, e.g. p1p1
num /= S[i]

if num == 1  // if there are no prime factors left (i.e. all num's prime factors are in S)
return humble number```
You should have listened to this post here. Its much simpler than it looks

Code:
```for(i=0;i<length;i++){
while(num % S[i]==0)  num= num/ S[i];

}
if(num == 1) return 1;
else return 0;```

11. ok great it got it working!!! takes 108 seconds though. hmph thanks for the help. i need to get a faster algo.

12. I would greatly appreciate it if you share your method of thinking with me I have this assignment to do as well and I'm a bit lost. Please help

13. scroll up, anduril462's posts are basically what i did.

14. @nefsan: I sent you a PM but never heard back from you. Did you have any luck with a faster algorithm?

15. For test 1, I get the 50th humble number is 68. So I would dispute the sample test data.
Here they are:
2 3 4 6 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 26 27 28 30 32 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68

They are each divisible by at least one of the set 2 3 11 13 17.