Editorial: Counting Triplets

The problem requires counting ordered triplets a, b, c where a + b + c <= x and the sum is prime. A brute-force approach would be inefficient, so we optimize by precomputing primes and iterating efficiently.

We first generate all primes up to x. Then, we iterate over all possible values of a and b, checking if c = prime - (a + b) is valid. This avoids unnecessary calculations while ensuring order matters.

Time Complexity: O(x^2 * P) Where P is prime less than x.

Code :

#include <bits/stdc++.h>
using namespace std;

bool isitPrime(int n)//time complexity=O(sqrt(n))
{
	if(n==1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}

void solve()
{

		int n, m;
		cin >> n;
		vector<int>prime;
		for(int i = 3; i <= n; i++)
		{
				if(isitPrime(i))prime.push_back(i);
		}
		int ans = 0;
		for(int a = 1; a < n; a++)
		{
				for(int b = 1; b < n; b++)
				{
						for(auto it : prime)
						{
								int c = it - (a + b);
								if(a + b + c > n || c <= 0)
								{
										continue;
								}
								ans++;
						}
				}
		}
		cout << ans << endl;
}

int32_t main()
{
		ios::sync_with_stdio(false);cin.tie(0),cin.tie(0);
		int t = 1;
		// cin >> t;
		for (int tc = 1; tc <= t; ++tc)
		{
				// cout << "Case " << tc << ": ";
				solve();
		}
}