#1272 NumarareDP
Cerința
Nu există o descriere plictisitoare pentru această problemă, trebuie doar să se calculeze câte numere naturale în intervalul [A, B] au suma cifrelor un număr prim.
Date de intrare
Programul citește de la tastatură numerele A, B.
Date de ieșire
Programul va afișa pe ecran numărul căutat.
Restricții și precizări
1≤A,B≤1018
Exemplu
Intrare
4 19
Ieșire
6
Explicație
Cele 6 numere sunt 5, 7, 11, 12, 14, 16.
Răspunsuri la întrebare
Hmm, incerc sa fac o rezolvare optima, din cate vad nu rezultatul e problema ci viteza de executie. Revin cu un edit
#include <iostream>
using namespace std;
long long suma_cifrelor(long long x)
{
int s = 0;
while(x)
{
s = s + x%10;
x = x / 10;
}
return s;
}
long long prim(long long x)
{
if(x == 2)
return 1;
if(x<2)
return 0;
if(x%2 == 0)
return 0;
for(long long i=3;i*i<=x;i+=2)
if(x%i == 0)
return 0;
return 1;
}
void afisare(long long A, long long B)
{
int nr = 0;
for(long long i=A;i<=B;i++)
if(prim(suma_cifrelor(i)))
nr++;
cout<<nr;
}
int main()
{
long long A, B;
cin>>A>>B;
afisare(A, B);
return 0;
}