Author: SQU_Test
DIFFICULTY:
EASY
PREREQUISITES:
Basic programming, prime, sum, composite.
PROBLEM:
You can create a new task by generating some random math statement or modifying some theorems to get something new and build a new task from that. For example, the conjecture’s statement says: “each even number no less than four can be expressed as the sum of two primes”. Let’s modify it to: “each integer no less than 12 can be expressed as the sum of two composite numbers.” Not like the conjecture’s statement, we can prove this theorem.
You are given an integer n no less than 12; express it as a sum of two composite numbers.
EXPLANATION:
- One way to solve this is by bruteforce: there are O(n) different ways to decompose n as sum of two numbers. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation.
- And another way is try to prove this theorem. The solution is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number).
TIME COMPLEXITY:
Time complexity of the first solution is O(n) while the complexity of the second solution is O(1).
SOLUTIONS:
Setter’s Solution (First Method)
#include<iostream>
using namespace std;
bool isPrime(int n)
{
if(n>=4)
{
for(int i=2; i<n; i++)
{
if(n%i ==0)
return false;
}
}
return true;
}
int main()
{
int n;
cin>>n;
if(n%2==0)
{
if(!isPrime(n/2))
cout<<(n/2)<<" "<<(n/2)<<endl;
else
cout<<(n/2-1)<<" "<<(n/2+1)<<endl;
}
else
{
int x = n/2, y=n/2+1;
if(!isPrime(x) && !isPrime(y))
cout<<(n/2)<<" "<<(n/2+1)<<endl;
else
{
while(isPrime(x) || isPrime(y))
{
x--;
y++;
}
cout<<x<<" "<<y<<endl;
}
}
return 0;
}
Setter’s Solution (Second Method)
n = int(input())
if n%2 == 0:
print(8, n-8)
else:
print(9, n-9)