fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. using i64 = long long;
  5. using u32 = unsigned;
  6. using u64 = unsigned long long;
  7.  
  8. template <typename T>
  9. struct ExactDiv {
  10.   ExactDiv() {}
  11.   ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) {}
  12.   T mul_inv(T n) {
  13.     T x = n;
  14.     for (int i = 0; i < 5; ++i) x *= 2 - n * x;
  15.     return x;
  16.   }
  17.   friend T operator / (T n, ExactDiv d) { return n * d.i; };
  18.   bool divide(T n) { return n * this->i <= this->t; }
  19.   T t, i;
  20. };
  21.  
  22. ExactDiv<u64> ediv[200000];
  23.  
  24. bool is_odd_prime_slow(i64 n) {
  25.   for (i64 i = 3; i * i <= n; i += 2) {
  26.     if (n % i == 0) return false;
  27.   }
  28.   return true;
  29. }
  30.  
  31. bool is_odd_prime_fast(i64 n) {
  32.   for (i64 i = 3; i * i <= n; i += 2) {
  33.     if (ediv[i].divide(n)) return false;
  34.   }
  35.   return true;
  36. }
  37.  
  38. int main() {
  39.   for (int i = 1; i <= int(2e5); i += 2) ediv[i] = ExactDiv<u64>(i);
  40.  
  41.   i64 beg = 1e10 + 1;
  42.   i64 end = 1e10 + 2e5;
  43.  
  44.   clock_t t0 = clock();
  45.   int ans1 = 0;
  46.   for (i64 i = beg; i < end; i += 2) ans1 += is_odd_prime_slow(i);
  47.   clock_t t1 = clock();
  48.   int ans2 = 0;
  49.   for (i64 i = beg; i < end; i += 2) ans2 += is_odd_prime_fast(i);
  50.   clock_t t2 = clock();
  51.  
  52.   printf("%d %.3f sec\n", ans1, double(t1 - t0) / CLOCKS_PER_SEC);
  53.   printf("%d %.3f sec\n", ans2, double(t2 - t1) / CLOCKS_PER_SEC);
  54.   return 0;
  55. }
Success #stdin #stdout 4.57s 18360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8668 4.148 sec
8668 0.415 sec
https://ideone.com/SWG5lj
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!