# Sum of Digit as prime

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?

@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.

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.

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];

//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]=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];

q[n]=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[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={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;
}
}
}

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[j]*q[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;

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);

}
}

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