Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <algorithm>
- #define Nmax 15001
- #define ull unsigned long long
- using namespace std;
- ifstream fin("primequery.in");
- ofstream fout("primequery.out");
- unsigned long long V[Nmax] , C[Nmax] ;
- int D[Nmax];
- ull power(ull x, ull y, ull p)
- {
- ull res = 1;
- x = x % p;
- while (y > 0)
- {
- if (y & 1)
- res = (res*x) % p;
- y = y / 2;
- x = (x * x) % p;
- }
- return res;
- }
- bool miillerTest(ull d, ull n)
- {
- ull a = 2 + rand() % (n - 4);
- ull x = power(a, d, n);
- if (x == 1 || x == n-1)
- return true;
- while (d != n-1)
- {
- x = (x * x) % n;
- d *= 2;
- if (x == 1) return false;
- if (x == n-1) return true;
- }
- return false;
- }
- bool isPrime(ull n, ull k)
- {
- if (n <= 1 || n == 4) return false;
- if (n <= 3) return true;
- if(n == 5) return true;
- ull d = n - 1;
- while (d % 2 == 0)
- d /= 2;
- for (ull i = 0; i < k; i++)
- if (!miillerTest(d, n))
- return false;
- return true;
- }
- int main()
- {
- int n , k = 0;
- fin >> n;
- for(int i = 1 ; i <= n ; i++)
- {
- fin >> V[i];
- if(isPrime(V[i] , 600))
- C[++k] = V[i];
- D[i] = k;
- }
- for(int i = 1 ; i <= n ; i++)
- {
- int c = 0;
- for(int j = 1 ; j <= D[i] ; j++)
- {
- if(C[j] < V[i])
- c++;
- }
- fout << c << " ";
- }
- }
Add Comment
Please, Sign In to add comment