Sieve of Eratosthenes in C

// outputs prime numbers from 0 to 100

#include <stdio.h>
#include <math.h>

int main()
{
    int i, square_root, current_number;
    char is_prime[101]; // this array will have '1' for prime indexs and '0' for non-prime indexes

    is_prime[0] = '0';
    is_prime[1] = '0';

    square_root = sqrt(100);

    for(i = 2; i <= 100; i++) is_prime[i] = '1';

    for(i = 2; i <= square_root; i++)
    {
        if(is_prime[i] == '1')
        {
            current_number = i * i;

            while(current_number <= 100)
            {
                is_prime[current_number] = '0';
                current_number += i;
            }
        }
    }

    for(i = 0; i <= 100; i++)
    {
        if(is_prime[i] == '1') printf("%d\n", i);
    }

    return 0;
}



Comments

Popular posts from this blog

Timus 1209. 1, 10, 100, 1000... accepted solution in C

Timus Problem 1086. Cryptography Accepted Solution in C

Timus 1083. Factorials!!! Accepted Solution in C