daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest Aug 12th, 2017 50 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
Top