pastebin

Paste Search Dynamic
Recent pastes
is prime
  1. #include <iostream>
  2. #include <numeric>
  3. #include <algorithm>
  4. #include <math.h>
  5. using namespace std;
  6. #define N 10000005
  7. bool is_prime[N];
  8. void sieve(int n) {
  9.  
  10.     is_prime[0] = is_prime[1] = false;
  11.       for(int i = 2; i <= n; i++)is_prime[i] = true;
  12.  
  13.     for(long long i = 2; i <= n; i++)
  14.         if(is_prime[i])
  15.             for(long long k = i*i; k <= n; k+=i)
  16.                 is_prime[k] = false;
  17.  
  18. }
  19. long long gcd(long long a, long long b) {
  20.   while (b != 0)  {
  21.     long long t = b;
  22.     b = a % b;
  23.     a = t;
  24.   }
  25.   return a;
  26. }
  27.  
  28. int main() {
  29.     sieve(1e7);
  30.     int n;
  31.     long long x,lcm=0,lcmnew=1e9,lcmpast=0,a,b,lcm1=1e9,lcm2=1e9,a1,aa,a2,b1,bb,b2;
  32.     cin>>n;
  33.     while(n--){
  34.         lcmnew=1e9;lcm1=1e9;lcm2=1e9;
  35.         cin>>x;
  36.         if(is_prime[x]){
  37.             cout<<x-1<<" "<<"1n";
  38.             continue;
  39.         }
  40.         for(long long i=1;i<=sqrt(x);i++){
  41.             if(x%i==0){
  42.                 a1=i;
  43.                 b1=x-a1;
  44.                 a2=x/i;
  45.                 b2=x-a2;
  46.                 lcm1=(b1*a1)/gcd(a1, b1);
  47.                 lcm2=(b2*a2)/gcd(a2,b2);
  48.                 if(lcm1<lcm2){
  49.                     aa=a1;
  50.                     bb=b1;
  51.                     lcmnew=lcm1;
  52.                 }
  53.                 else{
  54.                     aa=a2;
  55.                     bb=b2;
  56.                     lcmnew=lcm2;
  57.                 }
  58.                 if(lcmnew<lcmpast){
  59.                     lcm=lcmnew;
  60.                     a=aa;
  61.                     b=bb;
  62.                 }
  63.                 lcmpast=lcmnew;
  64.             }
  65.         }
  66.             cout<<b<<" "<<a<<endl;
  67.     }
  68. }
Parsed in 0.025 seconds