Search code examples
cprimessieve-of-eratosthenes

Prime numbers using Sieve of erastosthenes in C

I wrote the following program to display all prime numbers up to 150. It is not executing at all. what is so wrong with it?

# include <stdio.h>
int main(void)
{
    int p[150], i, j;

    for (i = 2; i < 150; i++)
        p[i] = 0;

    i = 2;


    while (i < 150){

        if (p[i] == 0)
            printf("%i ", i);

        for (j = 1; i*j <= 150; j++)
            p[i*j] = 1;

        i++;
    }

    return 0;
}
Solution

  • i*j <= 150 is incorrect, it should be i*j < 150, because the p array has elements from 0 to 149. The program gets stuck in an infinite loop because of this.

    EDIT: The rest of this answer was incorrect, so I've removed it.