Basic Array help

This is a discussion on Basic Array help within the C Programming forums, part of the General Programming Boards category; I checked some prev. threads but I didn't find what I'm looking for... sorry if this is a repost. I ...

  1. #1
    Registered User
    Join Date
    Jul 2002
    Posts
    44

    Basic Array help

    I checked some prev. threads but I didn't find what I'm looking for... sorry if this is a repost. I understand single dimension arrays... and second dimension arrays (not as well as single though), but that's beyond the point. My homework this time is to create a program which will list the PRIME number from 1-200... I'm kinda dumbed with the logic I need to use. A prime number can ONLY be divided by itself and one. All numbers, though can be diveded by itself and one... so I'm kinda confused as to how to seperate the two... maybe a remiender operator? I haven't really attempted anything worth seeing... just some basic for loops that would print out 1-200 and a condition to sep primes from normal numbers (that condition is blank though). Yeah, so basically I need to print out the prime numbers 1 through 200 using a single dimension array. TIA.

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    this is more of a math question you have me thinks, the computational methods involved in finding primes
    hello, internet!

  3. #3
    Registered User
    Join Date
    Jul 2002
    Posts
    45
    Show us what you have so far and then maybe we can offer some advice on how to work the problem.

  4. #4
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    There's a lot of ways to do it.

    here's a sloppy one.

    2 is the only even number that is prime.

    so if the number is greater than 2, and it's even, you could ignore it. otherwise you could check every value less the given one until half the given value.

    Code:
    #define TRUE  1
    #define FALSE 0
    
    typedef int bool;
    
    bool prime(int value)
    {
           int count;
           if(value == 2||value == 1)
                   return TRUE;
          
           if(count % 2 == 0)      //if it's even
                  return FALSE;
           else
           {
                for(count = value/2; count < value;count++)
                {
                       if( value % count == 0)
                              return FALSE;
                }
           }
           return TRUE;
    }

  5. #5
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    faster way to do it, but before you call isprime (i) you have to call isprime (i) for all primes below i. my recursion also isnt self-starting but i think it could be easily

    Code:
    // wheee, i wrote this
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define PUT(x) myarray[(x-1)>>3] = myarray[(x-1)>>3] | (1 << ((x-1) % 8))
    #define GET(x) myarray[(x-1)>>3] & (1 << ((x-1) % 8))
    
    #define MAXNUMBER 50 // prints all primes from 1 to MAXNUMBER
    
    unsigned char myarray[(MAXNUMBER>>3)+1] = {0};
    
    #ifndef SLOWMETHOD
    
    int isprime (int i)
    {
      int j;
      for (j = 2; j < i; j++)
        if (GET (j)) // j is prime
          if ((i % j) == 0) // i is evenly divisible by j
            return 0; // i is not prime
      return 69; // i is prime
    }
    
    // this does the same thing but is slower
    // also you dont have to call isprime (x) for all primes
    // smaller than x first
    #else // ifndef SLOWMETHOD
    
    int isprime (int i)
    {
      int j;
      for (j = 2; j < i; j++)
        if ((i % j) == 0) // i is evenly divisible by j
          return 0; // i is not prime
      return 69; // i is prime
    }
    
    #endif // ifndef SLOWMETHOD
    
    int main (void)
    {
    
      int i;               
      printf ("Computing all primes from 1 to %i...\n", MAXNUMBER);
      PUT (2);
      PUT (3);
      PUT (5);  
    
      for (i = 6; i <= MAXNUMBER; i++)     
        if (isprime (i))
          PUT (i);
    
      printf ("Dun!  All primes from 1 to %i:\n", MAXNUMBER);
      for (i = 1; i <= MAXNUMBER; i++)
        if (GET (i))
          printf ("%i\n", i);
    
      printf ("--END--\n");
    
      return EXIT_SUCCESS;
    }
    hello, internet!

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    This is more of an algorithmic problem than anything else. Prime numbers are divisible by themselves and 1, nothing else. The brute force method is to loop through every number from N - 1 to 2 and check if N % current is 0. If it is then the number is not prime. What you need to do is find an algorithm for finding a prime (hint: www.google.com) and then write a function which checks each value from N - 1 to 2:
    Code:
    int i = 0;
    int primeArray[200] = {0};
    
    for ( current = N - 1; current > 1; current-- )
      primeArray[i++] = isPrime ( current );
    Then just print out the array. There are more efficient methods, but the oracle that is google can tell you about them, saving my poor little fingers the stress of detailing everything.

    -Prelude
    My best code is written with the delete key.

  7. #7
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    my code example has one main difference than the dog's and preludes: it takes advantage of the fact that you only have to test for divisiblity by all _prime_ numbers smaller than a number, not all numbers (unless you compile with -DSLOWMETHOD). this is not useful if you just want to find if a random number is prime, but if you have already found if all the numbers smaller than your test number are prime (for example if you're making a list of them), then it is faster.

    there are also advanced algorithms used with very large numbers that are beyond our scope.
    hello, internet!

  8. #8
    Registered User
    Join Date
    Jul 2002
    Posts
    44
    I'm really a newbie at C... and so far I didn't understand your method much, moi. I kind of understood dog... but what did you do when you typed in "typedef int bool;"? Thanks, to all of you and I'll do my best to figure it out...

  9. #9
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    this is easier to understand, but wastes memory:

    Code:
    // wheee, i wrote this
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define PUT(x) myarray[(x-1)] = 1
    #define GET(x) myarray[(x-1)]
    
    #define MAXNUMBER 50 // prints all primes from 1 to MAXNUMBER
    
    unsigned char myarray[MAXNUMBER] = {0};
    
    /* beyond this point use original code */
    hello, internet!

  10. #10
    Registered User
    Join Date
    Jul 2002
    Posts
    45
    If the code confuses you, I recommend you walk away from the computer with a blank piece of paper and a pencil, and sit down to figure out exactily what you are trying to accomplish.

    Start in general terms, then work towards more specifics. Then, look for patterns and ways to achieve your goal.

    You are looking for prime numbers up to 200. (It's good to know the outcome of your project before hand). Write them down in order on your paper.

    Look at the pattern. Prelude points out that primary numbers are only divisible by themselves. Therefore, any number divisible by a prime number is not prime. Perhaps you can figure out a way to get the number you wish to interrogate to be divided by the prime numbers you have discovered and check for a remainder. If the remainder is zero, it is not prime.

    Once you figure out a system. Go back to your computer and put your pencil language paper into c language.

    Then tweak the code.

    Have fun

  11. #11
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356

    this is for moi

    Moi u seem to confuse people man... Look at ur code .Do u think that a guy who has been programming for 2 months and just started arrays will understand that??Take it easy yoo it aint a contest ..

  12. #12
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946

    Re: this is for moi

    Originally posted by datainjector
    Moi u seem to confuse people man... Look at ur code .Do u think that a guy who has been programming for 2 months and just started arrays will understand that??Take it easy yoo it aint a contest ..
    the bit packing thing was copied from other code i had on hand. maybe it is too confusing. however the modified code which i posted below it is pretty simple imo.
    hello, internet!

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Or just find a list of all of the primes between 1 and 200, and stick them in the array when you initialize it:

    int array[] = { 1, 2, 3, 5, 7, 11, 13, 17... };

    But I doubt that's what your teacher wants.

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

  14. #14
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    Originally posted by quzah
    Or just find a list of all of the primes between 1 and 200, and stick them in the array when you initialize it:

    int array[] = { 1, 2, 3, 5, 7, 11, 13, 17... };

    But I doubt that's what your teacher wants.

    Quzah.
    BUHAHAHAAA
    hello, internet!

  15. #15
    Registered User
    Join Date
    Jul 2002
    Posts
    44
    Prelude...er.... what? Sorry to bother your tired fingers but google gave me crap. Yes, I'm shocked too, but I didn't find anything of use...

    What is N? N-1- ... gah, I'm confused man. And I've been programming for 4 weeks.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Basic array segmentation fault
    By Argentius in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2007, 04:50 AM
  2. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  3. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  4. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM

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