Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ull unsigned long long
  3. using namespace std;
  4.  
  5. ifstream fin("countprime.in");
  6. ofstream fout("countprime.out");
  7.  
  8. ull power(ull x, ull y, ull p)
  9. {
  10.     ull res = 1;
  11.     x = x % p;
  12.  
  13.     while (y > 0)
  14.     {
  15.         if (y & 1)
  16.             res = (res*x) % p;
  17.  
  18.         y = y / 2;
  19.         x = (x * x) % p;
  20.     }
  21.     return res;
  22. }
  23.  
  24. bool miillerTest(ull d, ull n)
  25. {
  26.     ull a = 2 + rand() % (n - 4);
  27.  
  28.     ull x = power(a, d, n);
  29.  
  30.     if (x == 1  || x == n-1)
  31.        return true;
  32.  
  33.     while (d != n-1)
  34.     {
  35.         x = (x * x) % n;
  36.         d *= 2;
  37.  
  38.         if (x == 1)      return false;
  39.         if (x == n-1)    return true;
  40.     }
  41.  
  42.     return false;
  43. }
  44.  
  45. bool isPrime(ull n, ull k)
  46. {
  47.     if (n <= 1 || n == 4)  return false;
  48.     if (n <= 3) return true;
  49.  
  50.     ull d = n - 1;
  51.     while (d % 2 == 0)
  52.         d /= 2;
  53.  
  54.     for (ull i = 0; i < k; i++)
  55.          if (!miillerTest(d, n))
  56.               return false;
  57.  
  58.     return true;
  59. }
  60. int main()
  61. {
  62.     ull k = 10 , a , b , c = 0;
  63.  
  64.     fin >> a >> b;
  65.     if(b < 0)
  66.         fout << 0;
  67.     else
  68.         if(a < 0)
  69.             a = 1;
  70.     else
  71.     for (ull i = a; i <= b; i++)
  72.         if (isPrime(i , k))
  73.             c++;
  74.  
  75.     fout << c;
  76. }
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. OK, I Understand
Top