greedy math number theory *1300

Please click on ads to support us..

Python Code:

def is_p(n):
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return i
    return True
for i in range(int(input())):
    n = int(input())
    imp = is_p(n)
    if n%2==0:
        print(n//2,n//2)
    elif imp==True:
        print(1,n-1)
    else:
        x = n//imp
        print(x,((n//x-1)*(x)))

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007;
bool prime(ll x)
{
	for(ll i=2;i<=sqrt(x);i++)
	{
		if(x%i==0) return false;
	}
	return true;
}
int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		
		if(n%2==0)
		{
			cout<<n/2<<" "<<n/2<<endl;
		}
		else if(prime(n)){
			 cout<<1<<" "<<n-1<<endl;
		}
		else {
			for(int i=2;i<=n-1;i++)
			{
				if(n%i==0)
				{
					cout<<(n/i)<<" "<<n-(n/i)<<endl;
					break;
				}
			}
		}
		
	}
}


Comments

Submit
0 Comments
More Questions

1374A - Required Remainder
1265E - Beautiful Mirrors
1296A - Array with Odd Sum
1385A - Three Pairwise Maximums
911A - Nearest Minimums
102B - Sum of Digits
707A - Brain's Photos
1331B - Limericks
305B - Continued Fractions
1165B - Polycarp Training
1646C - Factorials and Powers of Two
596A - Wilbur and Swimming Pool
1462B - Last Year's Substring
1608B - Build the Permutation
1505A - Is it rated - 2
169A - Chores
765A - Neverending competitions
1303A - Erasing Zeroes
1005B - Delete from the Left
94A - Restoring Password
1529B - Sifid and Strange Subsequences
1455C - Ping-pong
1644C - Increase Subarray Sums
1433A - Boring Apartments
1428B - Belted Rooms
519B - A and B and Compilation Errors
1152B - Neko Performs Cat Furrier Transform
1411A - In-game Chat
119A - Epic Game
703A - Mishka and Game