Sum of Digit as prime

1

Given a value N (0<=N<=10^50) we need to count number of pairs (a,b) 0<=a,b<=N such that sum of digit/s of a and b is prime.
EX: 12 2 is valid pair as 1+2+2=5 which is a prime .

Any IDEA how to solve it?

2

@uvaishzafri First make a function for identifying a prime number.
Then calculate the sum all digit of a and b and call the fuction. It seems a problem for beginner to me.
Please give me the problem link. Because, In your post you didn’t give much explanation.

4

Hi, I think it’s a combinatorics problem. Think of the problem as no. of values between 0 and x whose digits add to a prime.

5

Hi, hope you were you able to figure out how to solve it. If not, refer to my solution below. I have added comments wherever I felt them to be necessary. Please note that I didn’t handle the case of integer overflow (which is generally done by dividing with some big prime such as 10^9+7 or storing the integers as string). I have validated the output of my efficient solution by matching it with the output of the brute force solution (which works for small inputs). I am attaching that as well. Please let me know if there’s any alternate method you came across.

Happy to help,
Chenreddy

Efficient Solution

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    
    //First we calculate the # of whole numbers that 
    //are less than or equal to the input s 
    //for each possible sum of digits.
    
    int p[n+1][1000];
    
    //Here p[i][j] represents # of whole numbers that 
    //are of the form a(i),a(i+1),a(i+2),...,a(n-1) 
    //and sum of the digits is j.
    //Please note that a(i) can be zero.
    //p[n][j] is the base case.
    
    p[n][0]=1;
    for(int j=1;j<1000;j++)
    {
        p[n][j]=0;
    }
    
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<1000;j++)
        {
            p[i][j]=0;
            for(int k=0;k<=9;k++)
            {
                if(j-k>=0)
                {
                    p[i][j]+=p[i+1][j-k];
                }
                else
                {
                    break;
                }
            }
        }
    }
    
    /*
    for(int j=0;j<=50;j++)
    {
        cout<<j<<"\t";
        for(int i=0;i<=n;i++)
        {
            cout<<p[i][j]<<"\t";
        }
        cout<<"\n";
    }
    
    cout<<"\n";
    */
    
    
    
    //Here q[i][j] represents # of whole numbers that 
    //are of the form a(i),a(i+1),a(i+2),...,a(n-1) 
    //that are  <=    s(i),s(i+1),s(i+2),...,s(n-1)
    //and sum of the digits is j.
    //Please note that a(i) can be zero.
    //q[n][j] is the base case.
    
    
    int q[n+1][1000];
    
    q[n][0]=1;
    for(int j=1;j<1000;j++)
    {
        q[n][j]=0;
    }
    
    
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<1000;j++)
        {
            q[i][j]=0;
            
            int max_num=s[i]-'0';
            
            for(int k=0;k<max_num;k++)
            {
                if(j-k>=0)
                {
                    q[i][j]+=p[i+1][j-k];
                }
                else
                {
                    break;
                }
            }
            
            if(j-max_num>=0)
            {
                q[i][j]+=q[i+1][j-max_num];
            }
        }
    }
    
    /*
    for(int j=0;j<=50;j++)
    {
        cout<<j<<"\t";
        for(int i=0;i<=n;i++)
        {
            cout<<q[i][j]<<"\t";
        }
        cout<<"\n";
    }
    */
    
    
    //q[0][j] represents the # of whole numbers that 
    //are less than or equal to the input s 
    //and sum of the digits is j.
    
    
    //Generating the list of primes
    
    vector<int> prime;
    
    int flag[1000]={0};
    
    for(int i=2;i<1000;i++)
    {
        if(!flag[i])
        {
            prime.push_back(i);
            
            int j=2*i;
            
            while(j<1000)
            {
                flag[j]=1;
                j=j+i;
            }
        }
    }
    
    //Calculating the final answer
    
    int num_of_primes=prime.size();
    
    int ans=0;
    
    for(int i=0;i<num_of_primes;i++)
    {
        int sum=prime[i];
        
        int count=0;
        
        for(int j=0;j<=sum;j++)
        {
            count+=q[0][j]*q[0][sum-j];
        }
        //cout<<prime[i]<<" "<<count<<"\n";
        ans+=count;
    }
    
    cout<<ans<<"\n";
    
}

Brute Force Solution

#include <iostream>

using namespace std;

int sum_of_digits(int a)
{
    int ans=0;
    while(a)
    {
        ans+=(a%10);
        a/=10;
    }
    return ans;
}

int is_prime(int a)
{
    if(a<=1)    return 0;
    
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)  return 0;
    }
    
    return 1;
}


int main()
{
    int s;
    cin>>s;
    
    int answer=0;
    
    for(int i=0;i<=s;i++)
    {
        for(int j=0;j<=s;j++)
        {
            int sum_i=sum_of_digits(i);
            int sum_j=sum_of_digits(j);
            
            answer+=is_prime(sum_i+sum_j);
        }
    }
    
    cout<<answer<<"\n";
}
6

I Really Appreciate your serious concern regarding my problem.Thank You :slight_smile:

7

Welcome. It involved a lot of learning for me as well. Let me know if you have any doubts.

8

Problem is very good, but it was from Hackwithinfyi contest , right ? They only ask problems which are already on internet, one simple google search gives full solution with explanation : -algorithm - Special Pairs with sum as Prime Number - Stack Overflow

They should try to make their own questions.

{Also, this exact same problem has been asked at 4-5 places before, so I guess it got kinda famous)