Thread: Primes

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    26
    Rep Power
    0

    Primes


    Hello everyone!

    I've started today learning C, and I wanted to create a little script that would find all the primes up to 50, but it seems like it only prints uneven numbers...

    I can't find the mistake :/

    Code:

    Code:
    //gcc -o primes primes.c -lm
    
    #include <stdio.h>
    #include <math.h>
    
    int main(int argc, char *argv[])
    {
      int a = 1;
      int b = 2;
      
      while(a < 50) {
        float sa = sqrt(a)+1;
        while(b < sa) {
          float af = a;
          float bf = b;
          if(a/b == af/bf) {
            break;
          b++;
          }
        else {
          printf("%d is a prime!\n", a);
          break;
          }
        }
      b = 2;
      a++;
      }
      printf("\n");
      
      return 0;
    }
    Don't be to harsh, it's my first day and I find C a very confusing language (yet).

    Thanks in advance,

    Yegers

    PS: what exactly does b++; or a++: do? I know it ads 1 but can it also add 2?
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Location
    Iran
    Posts
    149
    Rep Power
    139
    Hi,


    Originally Posted by Yegers
    ... but it seems like it only prints uneven numbers ...
    Well, except 2, I don't know any other even prime number :)

    For me if a number N (N <> 2) has no divisor within the range [2 ; (N / 2) + 1] then that number is a prime number. Also what you're looking for is not the coefficient but the rest of the division (if the rest of the division between N and M is zero then M is a divisor of the N).

    So based on the above algorithm I would write something similar to this

    Code:
    #include <stdio.h>
    
    int main(int argc, char *argv[])
    {
        // integer values <= 50 to check for prime number
        int intValue = 2;
    
        // an array in which we put the prime numbers             
        int primes[100];
    
        // just an index value for exploring elements in the array             
        int indx = 0; 
    
        // if it is equal to 1 then the current number is a prime number
        int isPrimeFlag = 0;
    
        // shows, so far, how many prime number we have found       
        int primeCounter = 0;     
    
    
        while (intValue < 50)
        {
            // So this is the range, that is, for each intValue we have to search for
            // possible divisor within the range of [2; (intValue / 2) + 1] 
            int divTestLimit = (intValue / 2) + 1;
            int divisor = 2;
    
            isPrimeFlag = 1;
       
            while (divisor <= divTestLimit)
            {
                if (((intValue % divisor) == 0) && (intValue != 2))
                {
                    // So there was a divisor, therefore, it is not a prime number
                    isPrimeFlag = 0;
    
                    // Because, we already have found a divisor, it is useless to continue
                    // the search, we simply leave the inner while loop by break
                    break;
                }
    
                // The next possible divisor
                ++divisor;
            }
            
            if (isPrimeFlag)
            {
                primes[primeCounter] = intValue;
                ++primeCounter;
            }
            ++intValue;
        }
    
        for (indx = 0 ; indx < primeCounter ; indx++)
            printf("%d, ", primes[indx]);
        
        printf("\n");
    
        return 0;
    }

    Which gives the following result

    Code:
    $ gcc -Wall testscript.c -o testscript
    $ ./testscript
    $ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
    $

    Regards,
    Dariyoosh
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    26
    Rep Power
    0
    Many thanks for the answer!

    How does a for-loop in C work exactly?

    In python it's just:

    Code:
    for i in list:
      #do something
    But how would that be in C?

    Code:
    for(i=0; ???; i++) {
      //do something
      }
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,158
    Rep Power
    2222
    C doesn't have a foreach (what what you described is called in other languages).

    Your overall syntax is completely wrong, since the three expressions are delimited by semicolons, not by colons.

    for (<initialization>; <test expression>; <iterative expression>)

    The initialization expression is evaluated only once, at the start of the loop. Then the loop begins with the evaluation of the test expression; if it evaluates as true, then the loop is executed. At the end of the loop, the iterative expression is evaluated, then we're back to the top of the loop and the evaluation of the test expression.

    A simple example would be i iterating ten times:
    for (i=0; i < 10; i++)

    More complexly, we could have multiple initializations, etc:
    for (i=0, j=i+1; i<10 && j < i; i++, j+=2)
  8. #5
  9. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Location
    Iran
    Posts
    149
    Rep Power
    139
    Originally Posted by Yegers
    ... How does a for-loop in C work exactly? ...
    I think the you should take a look at (at least) one of the following books (just examples among many others):

    http://publications.gbdirect.co.uk/c_book/the_c_book.pdf

    http://www.amazon.com/C-Nutshell-OReilly-Peter-Prinz/dp/0596006977/ref=sr_1_1?s=books&ie=UTF8&qid=1360402760&sr=1-1&keywords=c+in+a+nutshell

    http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628/ref=sr_1_1?s=books&ie=UTF8&qid=1360402653&sr=1-1&keywords=c+programming


    Regards,
    Dariyoosh
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    26
    Rep Power
    0
    Well many thanks for the suggestions^^'

    I'll look into C syntax a bit more, it looks like there is still a long way to go

    Kind regards,

    Yegers

IMN logo majestic logo threadwatch logo seochat tools logo