From 2a7bc10f6c011d19fb3b0e73068f7e1a9c30ace0 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Sat, 8 Oct 2016 09:56:43 +0700 Subject: Initial commit --- NTU/pi.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 NTU/pi.c (limited to 'NTU/pi.c') diff --git a/NTU/pi.c b/NTU/pi.c new file mode 100644 index 0000000..0dc8a1e --- /dev/null +++ b/NTU/pi.c @@ -0,0 +1,53 @@ +#include +#include +#include + +int main() +{ + long i, j; + char prime[44712] = {0, 0, [2 ... 44711] = 1}; + for (i = 2; i < 212; i++) + if (prime[i]) + for (j = i * i; j < 44712; j += i) + prime[j] = 0; + + + long primes[4648]; + j = 0; + for (i = 0; i < 44712; i++) + if (prime[i]) + primes[j++] = i; + + long l, r; + scanf("%ld %ld", &l, &r); + + long imax = (long) sqrt(r); + for (i = 0; i < 4648; i++) + if (primes[i] > imax) { + imax = i; + break; + } + + r -= l - 1; + long *list = malloc(r * 4); + for (i = 0; i < r; i++) + list[i] = 1; + + long prime0, l0; + for (i = 0; i < imax; i++) { + prime0 = primes[i]; + l0 = (l % prime0) ? (prime0 - (l % prime0)) : 0; + l0 = (l + l0 > prime0 * prime0) ? l0 : (prime0 * prime0 - l); + for (j = l0; j < r; j += prime0) + list[j] = 0; + } + + long val = 0; + for (i = 0; i < r; i++) + if (list[i]) + val++; + + printf("%ld\n", val); + + return 0; +} -- cgit 1.4.1