PROBLEM LINK:
Author: Gautam Nahar
DIFFICULTY:
Simple
PREREQUISITES:
PROBLEM:
You are given an integer N, your task is to find number of good tuples that can be formed by integers from 1 to N.
A tuple (X,Y,Z) is considered good if it consists of three prime numbers X, Y and Z
such that X<Z<Y≤N and X+Z=Y.
EXPLANATION:
Since all prime numbers are odd integers except 2, and we can never represent 2 as the summation of the other two primes, as it is the smallest prime number. Hence we say that in any good tuple (X,Y,Z) the integer Y is always an odd integer such that X+Z=Y.
As, we know that:
Since our Y is always Odd, it means either X or Z needs to be Even to form a good tuple. As X and Z, needs to be prime numbers too, hence there is only one valid choice left i.e X needs to be 2.
Hence Z will be equal to Y-2, for a tuple to be good Z needs to be prime number. Now, we can slightly re-frame our task as:
Given a integer N, we need to calculate such numbers say Y, such that Y and Y-2 are prime numbers and are less than N.
Rest is implementation which can be done by finding all prime numbers before hand and then checking for every integer, say Y. If we found Y and Y-2 to be prime number then we increment our answer. We also need to pre-calculate all answers for every N before hand as not doing so will result in TLE since T*N is large enough.
TIME COMPLEXITY:
O(N*log(N)) for pre-computation and O(1) for answering every query afterwards.
SOLUTIONS:
Setter
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
const int N=1000001;
bool seive[N];
memset(seive,true,sizeof(seive));
for(int i=2;i*i<=N;i++){
if(seive[i]){
for(int j=i*i;j<=N;j+=i){
seive[j]=false;
}
}
}
int ans[N]={0};
int count=0;
for(int i=5;i<N;i++){
if(seive[i] and seive[i-2])
count++;
ans[i]=count;
}
int t;
cin>>t;
while (t--)
{
int n;
cin>>n;
cout<<ans[n]<<"\n";
}
}