From 0887d8f96950a060a122e14ed2981182ff1eb37d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 28 Dec 2019 21:16:58 +0700 Subject: [usth/ICT2.1] Algorithm and Data Structures --- usth/ICT2.1/labwork/4/Ex2.c | 46 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 usth/ICT2.1/labwork/4/Ex2.c (limited to 'usth/ICT2.1/labwork/4/Ex2.c') diff --git a/usth/ICT2.1/labwork/4/Ex2.c b/usth/ICT2.1/labwork/4/Ex2.c new file mode 100644 index 0000000..6ad6b87 --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex2.c @@ -0,0 +1,46 @@ +/* + * Read n from stdin and print all primes from 1 to n to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include + +void subsieve(int *mask, int n, int i, int j) +{ + if (j > n) + return; + mask[j] = 1; + subsieve(mask, n, i, i + j); +} + +void sieve(int *mask, int n, int i) +{ + if (i * i > n) + return; + if (!mask[i]) + subsieve(mask, n, i, i + i); + sieve(mask, n, i + 1); +} + +void print_primes(int *mask, int n) +{ + if (!n) + return; + if (!mask[n]) + printf("%d\n", n); + print_primes(mask, n - 1); +} + +int main() +{ + int n; + scanf("%d", &n); + + int *notprime = calloc(n + 1, sizeof(int)); + notprime[0] = notprime[1] = 1; + sieve(notprime, n, 2); + print_primes(notprime, n); + + return 0; +} -- cgit 1.4.1