What is the best way to generate prime numbers?

Question

I am doing exercises from Programming in C by Kochan; just at the initial stage, chapter 5.

Here is the task:

Program 5.10 has several inefficiencies. One inefficiency results from checking even numbers. Because it is obvious that any even number greater than 2 cannot be prime, the program could simply skip all even numbers as possible primes and as possible divisors. The inner loop is also inefficient because the value of p is always divided by all values of d from 2 through. This inefficiency could be avoided by adding a test for the value of is_prime in the conditions of the for loop. In this manner, the for loop could be set up to continue as long as no divisor was found and the value of d was less than p. Modify Program 5.10 to incorporate these two changes.

Here is Program 5.10

    // generate a table of prime numbers
    #include <stdio.h>

    int main (void)
    {
        int p, d;
        _Bool is_prime;

        for (p = 2; p <= 50; ++p)
        {
            is_prime = 1;

            for (d = 2; d < p; ++d)
                if (p % d == 0)
                    is_prime = 0;

                if (is_prime)          // or if (is_prime != 0); same
                    printf ("%i ", p);
        }

        printf ("\n");
        return 0;
    }

Here are two options I am trying to write, but both print out blank space; no numbers are produced. The first one might represent a completely wrong approach, but I can't see why the second wouldn't work.

Option 1:

 // generate a table of prime numbers
#include <stdio.h>
#include <stdbool.h>

int main (void)
{
    int p, d;
    bool is_prime;

    /* start from p=2, do until p is less than 50,

     and skip all even numbers */

    for (p = 2; (p < 50) && (p % 2 != 0); ++p)

    {
        is_prime =1;

        /* the inner for loop says: start from d = 2; do until
         d is less than p, and also test if p is prime or not by
         dividing p by d */

        for (d = 2; d < p (p % d != 0 ? is_prime : !is_prime); ++d)

             printf ("%i ", p);
    }

    printf ("\n");
    return 0;
}

Option 2:

// generate a table of prime numbers
#include <stdio.h>
#include <stdbool.h>

int main (void)
{
    int p, d;
    bool is_prime;

    /* start from p=2, do until p is less than 50,

     and skip all even numbers */

    for (p = 2; (p < 50) && (p % 2 != 0); ++p)

    {
        is_prime =1;

        /* the inner for loop says: start from d = 2; do until
         d is less than p, and also test if p is prime or not by
         dividing p by d */

        for (d = 2; (d < p) && (p % d != 0); ++d )
            /* this inner loop was supposed to print the number if
             it is not divided by d */

            printf ("%i ", p);
    }

    printf ("\n");
    return 0;
}

I would be grateful for your help! I am new to programming.

Thank you!

Answer 1

Hmmm....

#include <stdio.h>
#include <stdbool.h>
int main(void) {
  unsigned int d = 0;
  unsigned int p = 0;
  bool is_prime = false;
  // We know 2 is prime
  printf( "%u ", 2 );
  for (p = 3; p < 50; p += 2 ) {
    // Skipped even numbers
    is_prime = true;
    // Since 2 is prime and we got rid of even numbers
    // We can just check odd divisors by starting with 3 and incrementing by 2
    for (d = 3; d * d < p && is_prime == true; d += 2) {
      // If we have a divisor, it's not prime
      if (p % d == 0) {
        is_prime = false;
      }
    }
    // This was outside the loop in the original program
    if (is_prime) {
      printf("%u ", p);
    }
  }
  return 0;
}

First, we know 2 is our only even prime, so to simplify, we go ahead and print it and start with 3. Since no other even number is prime, we increment by 2 each looping (remember -- a for loop stops when the condition is false, so we cannot say p % 2 != 0 as the loop condition). We set is_prime to true then test all odd divisors. If a divisor is found, the number isn't prime and we stop testing; otherwise, the number is prime. Again, since 2's the only even prime, we can skip even divisors. Finally, if we're past the square root of the number, then the number is guaranteed to be prime.

Answer 2

Since you are still learning, I would consider breaking down some pieces, for example creating a isPrime function, e.g.:

int isPrime(int num) {
    int i;
    for (i = 2; i < num; i++) {
        if (num % i == 0 && i != num) 
            return 0;
    }
    return 1;
}

Then, you can use it into your approaches, e.g.:

#include <stdio.h>

int main()
{
    int p, d;

    /* Avoid (p == 2) comparison each iteration */
    printf ("2 ");

    /* Go from 3 to 49 and print prime numbers without checking even numbers */
    for (p = 3; p < 50; ++p) {
        if (p % 2 != 0){
            if (isPrime(p))
                printf ("%i ", p);
        }
    }

    return 0;
}

Of course there are many different ways and you should consider using some time library (perhaps time.h) for performance evaluation.

Answer 3

The issue in your code is your first for-loop guard. The loop I'm referencing:

for (p = 2; (p < 50) && (p % 2 != 0); ++p)

If you look closely at the guard, you'll see that it will start false. Using your initial value of p = 2, you get this expansion of the loop guard

(2 < 50) && (2 % 2 != 0) == true && (0 != 0) == true && false == false Therefore, because your loop guard is initially false, the loop will never run.

If you want the solution, it seems like the other two answers to this question have provided something that is stylistically better than what you have written (style is important in programming) and correct.

Answer 4

#include<stdio.h>
int main()
{
  int N,x,y,i1,i2,isprime;
  x=y=2;
  i1=i2=1;
  isprime=1;
  scanf("%d",&N);
  while(x<=N)
  {
       while(y*y<=x)
       {
         if(x%y==0 && x!=y)
         {
            isprime=0;
            break;
         }
         y+=i2;
         i2=2;
       }
       if(isprime==1)
       {
             printf("\t%d",x);
       }
       x+=i1;
       i1=2;
       y=3;
       isprime=1;
  }
  return 0;
}