Thread: big number problem

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    54

    big number problem

    I wrote a program to solve one of the questions at the euler project ..

    it asks to add all the primes under two million ..

    I wrote a program and tried the answer .. got it wrong a few times .. rewrote the program and got it wrong a few more times ..

    so Im thinking I may have the wrong data type I have used int .. long int and usigned int ..

    hopefully someone can spot where Im going wrong and put me on the right track ..

    anyway heres my code
    Code:
    /*   objective sum all primes under two million using sieve method */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 2000000
    int find_ans( unsigned int*fp ){
         unsigned int count,d = 0,sum = 0;
    
         for( count = 2; count < MAX; ++count ){
              if( *( fp + count ) == 1 ){
                   ++d;
                   sum = sum + count;
                   printf("%i          %i\n",count,sum );
                }
         }
         printf("find_ans\n");
         printf("number of primes %li sum %li\n",d,sum );
    }
    int find_prime( unsigned int count, unsigned int *fp ){
    //     printf("find_prime\n");
         unsigned int countR = 2 * count;
    
         for( countR; countR <= MAX; countR += count ){
             *( fp + countR ) = 0;
             }
    }
    int sieve( unsigned int *fp ){
         printf("sieve\n");
         unsigned int count;
    
         for( count = 2; count < MAX; ++count ){
              if( *( fp + count ) == 1 ){
                   find_prime( count, fp );
              }
         }
         find_ans( fp );
    }
    int make_array( unsigned int *fp ){
         int count;
    
         printf("make_array\n");
         for( count = 0; count < MAX; count++ ){
              *( fp + count ) = 1;
         }
         sieve( fp );
    }
    int allocate_memory(){
         unsigned int *fp;
    
         printf("allocate_memory\n");
    
         fp = ( unsigned int *) malloc( MAX*sizeof( unsigned int ));
         if( fp == NULL ){
              fprintf(stderr, "out of memory\n");
              exit ( 1 );
              }
         make_array( fp);
         free( fp );
    }
    int main( int argc, char * argv[] ){
         allocate_memory();
         getchar();
         return( 0 );
    }
    any help appreciated .. thanks al.

    ps not looking for the answer just hints on my programming ..

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Note that is considered extraordinarily bad programming practice to daisy-chain your functions together the way you have. There is no good reason -- there isn't even a bad reason -- for your make_array function to call sieve, for instance.

    As to the question, you seem to be printing out all the sums -- do you see any overflow (where the number wraps around)? If not, then you should be ok there.

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    1
    Besides several compiler warnings, use double for the sum and it'll be fine for this exercise, but take a look at GMP for the other exercises. You'll need it.

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Also, (although this has nothing to do with your problem) I noticed that all your functions are supposed to return an int but there is no return statement in any of them. Specify a void return type if you don't want to return anything (except for main() which has to return an int).

  5. #5
    Registered User
    Join Date
    Aug 2006
    Posts
    54

    kk

    thanks for all the props up ..

    taken all comments into consideration and heres what I have come up with ..
    Code:
    /*   objective sum all primes under two million using sieve method */
    
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 2000000
    
    void find_ans( unsigned int*fp ){
         unsigned int count,d = 0,sum = 0;
    
         for( count = 2; count < MAX; ++count ){
              if( *( fp + count ) == 1 ){
                   ++d;
                   sum = sum + count;
                   printf("%i          %i\n",count,sum );
                }
         }
         printf("find_ans\n");
         printf("number of primes %li sum %li\n",d,sum );
    }
    void find_prime( unsigned int count, unsigned int *fp ){
         unsigned int countR = 2 * count;
    
         for( countR; countR <= MAX; countR += count ){
             *( fp + countR ) = 0;
             }
    }
    void sieve( unsigned int *fp ){
         printf("sieve\n");
         unsigned int count;
    
         for( count = 2; count < MAX; ++count ){
              if( *( fp + count ) == 1 ){
                   find_prime( count, fp );
              }
         }
    }
    void make_array( unsigned int *fp ){
         int count;
    
         printf("make_array\n");
         for( count = 0; count < MAX; count++ ){
              *( fp + count ) = 1;
         }
    
    }
    int main( int argc, char * argv[] ){
         unsigned int *fp;
    
         fp = ( unsigned int *) malloc( MAX*sizeof( unsigned int ));
         if( fp == NULL ){
              fprintf(stderr, "out of memory\n");
              exit ( 1 );
              }
    
         make_array( fp );
         sieve( fp );
         find_ans( fp );
         free( fp );
    
         getchar();
         return( 0 );
    }
    I did try using sum as a double but it returned a negative number ..

    the reason I was printing each prime and sum was I was considering whether the sum was overflowing and it does indeed go into negative numbers around the 230,000 prime mark ..

    before that I was printing out the total sum ..

    hope the code is better this time round .. still does not give the right answer though ..

    any help as I said earlier appreciated .. al.

  6. #6
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Did you try "unsigned long long" ? (64-bit unsinged. Maybe (just maybe) it will be enough).

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Also, if you're going to use unsigned ints, print them as unsigned ints! (use either the "%llu" or "%I64u" format specifier depending on your system)

  8. #8
    Registered User
    Join Date
    Aug 2006
    Posts
    54
    I have used ints &#37;i long ints %li long long ints %lli and unsigned ints %u all give me the same wrong answer ..

    Im using a pentium 1 166 running windows 98 and dev-cpp 4.9.9.2

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > and it does indeed go into negative numbers around the 230,000 prime mark
    With what - long or long long?

    > I have used ints &#37;i long ints %li long long ints %lli and unsigned ints %u all give me the same wrong answer .
    You will need "%I64u" to print a long long in dev-c++.
    It uses the microsoft C library (with all it's bugs and features), rather than glibc (with all it's bugs and features).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Registered User
    Join Date
    Aug 2006
    Posts
    54

    thanks ..

    thanks for the help .. I aprreciate it .. using salems "%I64u" to print out a long long I got the right answer ..

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    another issue is that you are storing the sum in an int, which has a limti of 2 billion something. The answer is much grater than that so tyou will get an overrun condition.

    you have to use __int64 or the equivelant.


    nvm, just noticed you already covered this issue.

  12. #12
    Registered User
    Join Date
    Jul 2008
    Posts
    38
    However the long long modifier was introduced in the C99 standard; some compilers had already supported it. Be sure to check if your compiler supports C99.

    Max value of long int = +2,147,483,647
    Max value of unsigned long int = 4,294,967,295
    Max value of long long = +9,223,372,036,854,775,807
    Max value of unsigned long long = 18,446,744,073,709,551,615

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Number theory problem
    By elad in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 09-02-2004, 10:02 AM
  2. Small Problem that could be a big problem
    By sytaylor in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2004, 09:49 AM
  3. number ouput problem...
    By o0obruceleeo0o in forum C++ Programming
    Replies: 7
    Last Post: 11-17-2002, 06:56 AM
  4. problem with my prime number program
    By datainjector in forum C Programming
    Replies: 4
    Last Post: 07-12-2002, 12:30 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM