-
Notifications
You must be signed in to change notification settings - Fork 0
/
soe.c
94 lines (83 loc) · 2.55 KB
/
soe.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// soe.c Sieve of Eratosthenes - find primes up to n
// Inspired by: https://www.youtube.com/watch?v=klcIklsWzrY
//
// Build:
// $ gcc -Wall -Wextra -Wpedantic -o soe soe.c -lm
//
// Run:
// $ ./soe 100
//
// TODO:
// Simplify solution
// Don't use prime status flag (bool mark)
// Print all numbers, display primes differently from non-primes
// Print using grid
// Use stderr for errors
//
// Example sieve with prime numbers visible and non-primes hidden:
//
// ┌──┬──┬──┬──┬──┬──┬──┐
// │ 0│ 1│ 2│ 3│ │ 5│ │
// ├──┼──┼──┼──┼──┼──┼──┤
// │ 7│ │ │ │11│ │13│
// ├──┼──┼──┼──┼──┼──┼──┤
// │ │ │ │17│ │19│ │
// ├──┼──┼──┼──┼──┼──┼──┤
// │ │ │23│ │ │23│ │
// ├──┼──┼──┼──┼──┼──┼──┤
// │ │29│ │ │ │ │ │
// ├──┼──┼──┼──┼──┼──┼──┤
// │ │ │37│ │ │ │41│
// ├──┼──┼──┼──┼──┼──┼──┤
// │ │43│ │ │ │ │ │
// └──┴──┴──┴──┴──┴──┴──┘
//
////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <unistd.h>
#define MAXN 1000
// numbers and prime status
struct sieve {
int n; // the number
bool mark; // prime == false
};
int main(int argc, char *argv[]) {
int n;
struct sieve *siv = NULL;
// check arguments
if (argc != 2) {
printf("%s: argument error. use: %s n\n", argv[0], argv[0]);
return 1;
}
if ((n = atoi(argv[1])) > MAXN) {
printf("%s: argument error, max n = %d\n", argv[0], MAXN);
return 2;
}
// storage for numbers and prime status
siv = (struct sieve *)malloc((sizeof(struct sieve) * n) + 1);
if (siv == NULL) {
printf("%s: memory error\n", argv[0]);
return 3;
}
// init memory
for (int i = 0; i <= n; i++) {
siv[i].n = i;
siv[i].mark = false;
}
// Use the sieve to calculate primes
for (int i = 2; i <= n; i++)
for (int j = 2; j <= sqrt(i); j++)
if (((i % j) == 0) && (siv[i].mark == false))
siv[i].mark = true;
// unmarked numbers are primes
for (int i = 0; i <= n; i++) {
if (!siv[i].mark)
printf("%d ", siv[i].n);
}
printf("\n");
free(siv);
return EXIT_SUCCESS;
}