Skip to content

Instantly share code, notes, and snippets.

@efeciftci

efeciftci/sieve_of_eratosthenes.c

Last active December 13, 2023 10:28
Show Gist options
  • Save efeciftci/c88b0a461ff99e7df642501147d8cd8c to your computer and use it in GitHub Desktop.
Save efeciftci/c88b0a461ff99e7df642501147d8cd8c to your computer and use it in GitHub Desktop.
Download ZIP
Animated Sieve of Eratosthenes prime number finder program in C.
Raw
sieve_of_eratosthenes.c
// Sieve of Eratosthenes:
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <stdio.h>
#include <stdlib.h>
// https://github.com/tapio/rlutil
#include "rlutil.h"
int N, *numbers, nrOfDigits;
void printNumbers(int selectedIndex, int removedIndex) {
int lineLength = N <= 20 ? 5 : N <= 100 ? 10 : ((1 + (N - 1) / 100) * 5);
locate(1, 4);
for (int i = 0; i < N; ++i) {
if (i > 0 && i % lineLength == 0)
printf("\n");
if (numbers[i] == 0 || i < 1)
setColor(DARKGREY);
if (i == selectedIndex)
setBackgroundColor(BLUE);
else if (i == removedIndex) {
setBackgroundColor(RED);
setColor(GREY);
} else if (1 <= i && i < selectedIndex && numbers[i] != 0)
setBackgroundColor(GREEN);
printf("[%*d]", nrOfDigits, numbers[i]);
resetColor();
printf(" ");
}
printf("\n");
}
void eliminate() {
for (int i = 1; i < N; ++i)
if (numbers[i] != 0) {
locate(1, 3);
printf("Removing multiples of %d:", numbers[i]);
for (int j = i + 1; j < N; ++j)
if (numbers[j] != 0 && numbers[j] % numbers[i] == 0) {
printNumbers(i, j);
numbers[j] = 0;
msleep(250);
}
printNumbers(i, -1);
msleep(750);
}
}
void listPrimes() {
int printed = 0;
printf("\nPrime numbers found: {");
for (int i = 1; i < N; ++i)
if (numbers[i] != 0)
printf("%s%d", printed++ ? ", " : "", numbers[i]);
printf("}\n");
}
int main() {
int max;
cls();
printf("Enter N: ");
scanf("%d", &N);
hidecursor();
numbers = (int*) malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i) {
numbers[i] = i + 1;
}
max = N;
nrOfDigits = 1;
while ((max /= 10) != 0)
nrOfDigits++;
eliminate();
printNumbers(N, N);
listPrimes();
free(numbers);
showcursor();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment