• API
• FAQ
• Tools
• Archive
daily pastebin goal
68%
SHARE
TWEET

# Untitled

a guest Aug 12th, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2. #include <stdbool.h>
3. #include <stdlib.h>
4.
5. const int maxn = 2e8 + 7;
6. const int cache = 20000;
7.
8.
9. int if_compound[40000];
10.
11. int primes[15000];
12. int prime_end;
13.
14. void push_prime(int x) {
15.     primes[prime_end] = x;
16.     ++prime_end;
17. }
18.
19. int primes_size() {
20.     return prime_end;
21. }
22.
23. void set_bit(int i) {
24.     int num = i / 32;
25.     int bit = i % 32;
26.     if_compound[num] |= 1 << bit;
27. }
28.
29. int ask_bit(int i) {
30.     int num = i / 32;
31.     int bit = i % 32;
32.     return if_compound[num] == (if_compound[num] | (1 << bit));
33. }
34.
35. void clear() {
36.     int i = 0;
37.     for (i; i < 40000; ++i)
38.         if_compound[i] = 0;
39. }
40.
41. int min(int a, int b) {
42.     if (a < b)
43.         return a;
44.     else
45.         return b;
46. }
47.
48. int main() {
49.     int n, i, j, lst, x;
50.     lst = 0;
51.     scanf("%d", &n);
52.     int ans = 0;
53.     for (i = 2; i * i <= n; ++i)
54.         if (!ask_bit(i)) {
55.             ++ans;
56.             push_prime(i);
57.             for (j = i; j * j <= n; j += i)
58.                 set_bit(j);
59.         }
60.     int l = i;
61.     int r = min(l + cache, n + 1);
62.     while (l <= n) {
63.         clear();
64.         for (x = 0; x < primes_size(); ++x) {
65.             for (i = ((l + primes[x] - 1) / primes[x]) * primes[x]; i < r; i += primes[x]) {
66.                 set_bit(i - l);
67.             }
68.         }
69.         for (i = l; i < r; ++i)
70.             if (!ask_bit(i - l))
71.                 ++ans;
72.         l += cache;
73.         r = min(l + cache, n + 1);
74.     }
75.     printf("%d", ans);
76.     return 0;
77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top