Special Prime
LEVEL:Intermediate
Description
Given an integer N
N<=10^50
Print the no. of pairs (x,y) such that
0<=x<=n
0<=y<=n
F(x) +F(y) = Prime number
Where F(x) = sum of digits of x
Note : (x,y) and (y,x) are to be treated as same pair
Input Format
First line consists of a single integer
Output Format
Single consisting of a single integer
3
5
5
9
10
19
Login to see Discussion
Approach
Given a number n,
Maintain a set of pairs SET
Iterate i from 0 to n
Iterate j from 0 to n
Find if the sum of digits of i and sum of digits of j is a prime number
If the pair i,j is not present in SET,
Add it to SET
Finally print the number of sets in SET
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution