Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <bitset>
- using namespace std;
- ifstream fin ("emma.in");
- ofstream fout ("emma.out");
- bitset < 1000002 > mark;
- int v[80000];
- int main (){
- int prime = 1;
- v[prime] = 2;
- for (int i = 3; i <= 1000000; i += 2){
- if (!mark[i]){
- v[++prime] = i;
- for (int j = i + i; j <= 1000000; j += i)
- mark[j] = 1;
- }
- }
- int t, n;
- fin >> t;
- for (int i = 1; i <= t; ++i){
- fin >> n;
- int poz = 1;
- bool gasit = 0;
- while (v[poz] < n && !gasit){
- int x = n - v[poz];
- int st = 1;
- int dr = prime;
- int mid;
- while (st <= dr && !gasit){
- mid = (st+dr)/2;
- if (v[mid]==x) gasit = 1;
- if (v[mid]<=x)
- st = mid + 1;
- else
- dr = mid - 1;
- }
- poz++;
- }
- if (gasit) fout << "DA\n";
- else fout << "NU\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement