Thread: 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]

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.

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

Code:

if((i==0) &&(num =initNum)) break;

= is assignment.
== is for equality testing.

Your code is ugly.


Quzah.