How many ways a number can be represented as sum of distinct primes

Question

Given a positive integer $ N,$ calculate the minimum number of distinct primes required such that their sum equals to $N.$ Also calculate the number of different ways to select these primes. Two ways are considered to be different iff there exists at least one prime in one set not existing in the other.

This problem is from SPOJ JPM2 - Just Primes II

I have a sub-optimal solution which is taking approx 20 seconds to produce the desired output. But this problem required 5 seconds in order to get accepted.

I got some hint from the problem setter that this problem required FFT implementation, however I am not able to reduce this problem to FFT.

any help will be appreciated. Below is my sub-optimal solution.

#include <bits/stdc++.h>
using namespace std;
#define MAX1 500002
#define MAX 500002


vector<bool> isPrime(MAX+1,1);
vector<uint> primes;
vector<uint>primeMap(MAX+1,0);
vector<uint>primeMap3(MAX+1,0);

inline void genPrimes(){
    
    isPrime[0] = isPrime[1] = 0;
    for(uint i=2;i*i<=MAX; i++){
        if(isPrime[i]){
            for(uint j=i;j*i<=MAX;j++){
                isPrime[i*j] = 0;
            }
        }
    }
    primes.push_back(2);
    for(uint i=3;i<=MAX;i+=2){
        if(isPrime[i]){
            primes.push_back(i);
        }
    }
    
    for(uint i=0;i<primes.size();i++){
        uint lb = upper_bound(primes.begin(),primes.end(),primes[i]) - primes.begin();
        for(uint j = lb ;primes[j]+primes[i]<MAX && j < primes.size();j++){
            primeMap[primes[i] + primes[j]]+=1;
        }
    }
    

    for(uint i=5;i < MAX1;i++){
        if(primeMap[i]){
            uint key = MAX1 - i;
            uint lb = upper_bound(primes.begin(),primes.end(),key) - primes.begin();
            uint p2 = primeMap[i];
            for(uint j=0;j<=lb;j++){
                if(primes[j] <= i && !isPrime[i-primes[j]] )
                primeMap3[i+primes[j]]+=(p2);
                else if(primes[j] < i)
                primeMap3[i+primes[j]]+=(p2-1);
                else
                primeMap3[i+primes[j]]+=(p2);
                
            }
        }
    }
}
inline int scan()
    {
    register int z=0;
    char c;
    do{ c=getchar_unlocked(); } while(c<'0');
    for(;c>='0';c=getchar_unlocked()) z = (z<<3) + (z<<1) + (c&15);
    return z;
 }
 
 inline void put_ull(int n) {
  char stack[44];
  int top = 0;
  if(n == 0) {
    putchar_unlocked('0');
  } else {
    while(n > 0) {
      stack[top++] = n % 10 + '0';
      n /= 10;
    }
    while(top > 0) {
      putchar_unlocked(stack[--top]);
    }
  }
  putchar_unlocked('\n');
}
int main() {
    
    genPrimes();
    
    int n,t,cs = 0;
    t=scan();
    while(t--){
        n=scan();
        if(isPrime[n]){
            printf("1 1\n");
        }else
        if(n > 2 && isPrime[n-2] && n!=4){
            putchar_unlocked('2');
            putchar_unlocked(' ');
            put_ull(primeMap[n]);
        }else
        if(primeMap[n]){
            putchar_unlocked('2');
            putchar_unlocked(' ');
            put_ull(primeMap[n]);
        }else
        if(primeMap3[n]){
            putchar_unlocked('3');
            putchar_unlocked(' ');
            put_ull((primeMap3[n] + 1)/3);
        }else{
            printf("-1 -1\n");
        }
    }
    return 0;
}

Answer 1

Probably FFT of how frequent certain breakdowns are: for example, no even number can be represented with an odd number of them, without using 2 . Same goes for odd numbers, and an even number of them. Also without using 2 or 3, the size of the difference between 1 mod 6 and 5 mod 6 primes, determines the remainder mod 6 of the sum. As for code optimizations, you can check isPrime[j] is nonzero, as if not, all it's multiples are also 0 already. if/else can be replaced by case statements unless slower. You don't need all the primes for some cases, 2 primes summing to an even number, only 0 mod 3 values when multiplied by 2 need all primes up to the multiple of 3 in mod 3 cases. Primes of form additive inverse of the even number over 2, plus that even number over 2, mod other values greater than 1, need not apply as the higher "prime" won't be a prime in the 2 prime case.