Algorithm
Problem link- https://www.spoj.com/problems/GONE/
GONE - G-One Numbers
The War of Evil vs Good continues and Ra-One and G-One continue to be on respective sides.
After saving all the cities with Ra-One Numbers G-One realised that some cities whose population is a "G-One Number" can be easy target for Ra-One.
A G-One number is a number sum of whose digits is a prime number
For example 12 .. sum = 1+2 = 3 ... 3 is a prime number.
G-One wants to find out all the populations which can be g-One numbers....
Can You help him.?
You will be given the range of population and you have to tell him how many in this range are G-One Numbers.
Input
first line has number 'c' indicating the number of ranges.
'c' lines follow and contain two numbers ... 'f' and 't' inclusive.
Output
Print a single line per case giving the number of populations which are G-One numbers.
Example
Input: 3
10 19
1 9
20 29
Output: 4
4
5
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 5e2+5;
string a, b;
int n;
int dp[12][100][2];
bool isPrime[MAXN];
void sieve(){
memset(isPrime, true, sizeof isPrime);
isPrime[0] = isPrime[1] = false;
for(int i = 2;i <= 1000; i++){
if(isPrime[i]){
for(int j = i*i;j <= 1000; j+=i)
isPrime[j] = false;
}
}
}
ll solve(string &s, int idx, ll sum, int isPrefixEqual){
if(dp[idx][sum][isPrefixEqual] != -1)
return dp[idx][sum][isPrefixEqual];
ll res = 0;
if(idx == n){
if(isPrime[sum])
res = 1;
}else{
if(isPrefixEqual){
for(int i = 0;i <= s[idx]-'0'; i++){
if(i == s[idx]-'0'){
res += solve(s, idx+1, sum + i, 1);
}else{
res += solve(s, idx+1, sum + i, 0);
}
}
}else{
for(int i = 0;i < 10; i++){
res += solve(s, idx+1, sum + i, 0);
}
}
}
dp[idx][sum][isPrefixEqual] = res;
return res;
}
int f(string &a){
bool odd = true;
ll sum = 0;
for(int i = (int)a.size()-1;i >= 0; i--){
sum += a[i] - '0';
}
return (isPrime[sum]);
}
int main(){
io;
sieve();
int t;
cin >> t;
while(t--){
cin >> a >> b;
memset(dp, -1, sizeof dp);
n = b.size();
ll ansR = solve(b, 0, 0, 1);
memset(dp, -1, sizeof dp);
n = a.size();
ll ansL = solve(a, 0, 0, 1);
ll ans = ansR - ansL + f(a);
cout << ans << endl;
}
return 0;
}Input
10 19
1 9
20 29
Output
4
5
Demonstration
SPOJ Solution-G-One Numbers-Solution in C, C++, Java, Python