Guest User

Untitled

a guest
Jan 19th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6. vector<int> p;
  7.  
  8. void erat(int n) {
  9. vector<int> sieve(n);
  10. for (int i=0;i<n;i++) sieve[i]=i;
  11. p.clear();
  12. for (ll i=2;i<n;i++) {
  13. if (sieve[i]==i) p.push_back(i);
  14. for (ll j=0;j<p.size() && p[j]<=sieve[i] && p[j]*i<n;j++)
  15. sieve[p[j]*i]=p[j];
  16. }
  17. }
  18.  
  19. int main () {
  20. int n;
  21. cin >> n;
  22. erat(n);
  23. for (int i=0,j=p.size()-1;i<=j;(p[i]+p[j]<n)?i++:j--)
  24. if (p[i]+p[j]==n) {
  25. cout << p[i] << ' ' << p[j];
  26. return 0;
  27. }
  28. }
Add Comment
Please, Sign In to add comment