Help with this please

This is a discussion on Help with this please within the C Programming forums, part of the General Programming Boards category; Ok so i have been coding this problem.The problem "> For a given set of K prime numbers S = ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    56

    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]
    Last edited by nefsan; 03-03-2011 at 09:37 PM. Reason: people are copying my code and teacher is raging wiht me :S

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    2,516
    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. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    56
    Quote Originally Posted by stahta01 View Post
    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. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    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. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    56
    Quote Originally Posted by anduril462 View Post
    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.
    Last edited by nefsan; 03-03-2011 at 07:13 PM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    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. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    56
    Quote Originally Posted by anduril462 View Post
    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;                              
    }
    Last edited by nefsan; 03-05-2011 at 05:50 PM. Reason: syntax erroor

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    if((i==0) &&(num =initNum)) break;
    = is assignment.
    == is for equality testing.

    Your code is ugly.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User Alienchicken's Avatar
    Join Date
    Feb 2009
    Posts
    22
    should have == there instead of =

  10. #10
    Registered User Alienchicken's Avatar
    Join Date
    Feb 2009
    Posts
    22

    Cool

    Quote Originally Posted by anduril462 View Post
    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. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    56
    ok great it got it working!!! takes 108 seconds though. hmph thanks for the help. i need to get a faster algo.

  12. #12
    Registered User
    Join Date
    Mar 2011
    Posts
    6
    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. #13
    Registered User
    Join Date
    Oct 2007
    Posts
    56
    scroll up, anduril462's posts are basically what i did.

  14. #14
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    @nefsan: I sent you a PM but never heard back from you. Did you have any luck with a faster algorithm?

  15. #15
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    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.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21