HackerRank Number Theory – Prime Sum

Challenge: Prime Sum

Subdomeniu: Number Theory (number-theory)

Scor cont: 70.0 / 70

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736447

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/prime-sum/problem

Cerinta

The problem is quite simple. You're  given a number N and a positive integer K. Tell if N can be represented as a sum of K prime numbers (not necessarily distinct).

**Input Format**  
The first line contains a single integer T, denoting the number of test cases.  
Each of the next T lines contains two positive integers, N & K, separated by a single space.  

**Output Format**  
For every test case, output "Yes" or "No" (without quotes).

**Constraints**  
1 <= T <= 5000   
1 <= N <= 10<sup>12</sup>   
1 <= K <= 10<sup>12</sup>    

**Sample Input**

    2
    10 2
    1 6

**Sample Output**

    Yes
    No

**Explanation**  

In the first case, 10 can be written as 5 + 5, and 5 is a prime number.
In the second case, 1 cannot be represented as a sum of prime numbers, because there are no prime numbers less than 1.

Cod sursa

//prime-sum.cpp
//Prime Sum
//Weekly Challenges - Week 3
//Author: derekhh

#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;

// k >= 3
bool Judge(long long n, long long k)
{
	if (n >= 4)
	{
		if (n % 2 == 0) return k <= n / 2;
		else return (k - 1) <= (n - 3) / 2;
	}
	return false;
}

long long modmult(long long a, long long b, long long mod)
{
	if (a == 0 || b < mod / a)
		return (a*b) % mod;
	long long sum;
	sum = 0;
	while (b>0)
	{
		if (b & 1)
			sum = (sum + a) % mod;
		a = (2 * a) % mod;
		b >>= 1;
	}
	return sum;
}

long long modpow(long long a, long long b, long long mod)
{
	long long product, pseq;
	product = 1;
	pseq = a%mod;
	while (b>0)
	{
		if (b & 1)
			product = modmult(product, pseq, mod);
		pseq = modmult(pseq, pseq, mod);
		b >>= 1;
	}
	return product;
}

bool MillerRabin(long long n, int seed)
{
	int k = 0;
	if (n < 2) return false;
	if (n == 2) return true;
	if (!(n & 1)) return false;

	long long m = n - 1;
	while (!(m & 1)) m >>= 1, k++;

	long long a = seed;
	a = modpow(a, m, n);
	if (a == 1 || a == n - 1) return true;
	
	for (int j = 0; j < k - 1; j++)
	{
		a = modpow(a, 2, n);
		if (a == 1) return false;
		if (a == n - 1) return true;
	}
	return false;
}

const int MAXN = 1000000;
bool isprime[MAXN + 10];

void Sieve()
{
	memset(isprime, true, sizeof(isprime));
	isprime[0] = isprime[1] = false;
	for (int i = 2; i*i <= MAXN; i++)
		if (isprime[i])
			for (int j = 2 * i; j <= MAXN; j += i)
				isprime[j] = false;
}

bool PrimalityTest(long long n)
{
	if (n <= MAXN)
		return isprime[n];
	else
		return MillerRabin(n, 2) && MillerRabin(n, 13) && MillerRabin(n, 23) && MillerRabin(n, 1662803);
}

int main()
{
	time_t start = clock();
	Sieve();
	int t;
	cin >> t;
	while (t--)
	{
		long long n, k;
		cin >> n >> k;
		if (k > 2)
			cout << (Judge(n, k) ? "Yes" : "No") << endl;
		else if (k == 2)
		{
			if (n % 2 == 0) cout << (n > 2 ? "Yes" : "No") << endl;
			else cout << (PrimalityTest(n - 2) ? "Yes" : "No") << endl;
		}
		else cout << (PrimalityTest(n) ? "Yes" : "No") << endl;
	}
	cerr << difftime(clock(), start) << endl;
	return 0;
}