Again About Prime Numbers (Editorial)

Written by @Tuncay_Pashayev.

In this problem there are two numbers $a$ and $b$. We have to find a prime number that it has the biigest sum of digits, between $a$ and $b$. If there are multiple prime numbers with same sum, we have to print biggest one. If there is no any prime number between $a$ and $b$ we have to print $-1$.

First we have to check if the number is prime. To do this we are going from 2 to square root of number. If there is no any divisor till there, that means there won't be any divisor bigger than square root and that means our number is prime, otherwise it is not prime. After checking of the number is prime or not, we have to find the number's sum of digits and print the biggest prime number that has it.

Implementation

int max_prime = -1, max_sum = -1;

Giving $-1$ to max_prime and max_sum, because if there won't be any prime number we have to print $-1$.

for (int i = a; i <= b; i++)

Checking all the numbers from $a$ to $b$.

if (i == 1)
    continue;

If $i$ is equals to $1$ we have to pass this, because $1$ is not a prime number.

bool is_prime = true;

Let's think that our number is prime.

for (int j = 2; j <= sqrt(i); j++)
{
    if (i % j == 0)
    {
        is_prime = false;
        break;
    }
}

Checking if there is a divisor between $2$ and square root of $i$. If there is at least one divisor, that means our number is not prime and there is no meaning to continue.

if (is_prime)

If our number is prime, we can find it's sum of digits.

int sum = 0, number = i;

Set the value of sum to $0$. If we do our operations with $i$, we can lose it's value.

while (number != 0)
{
    sum += number % 10;
    number /= 10;
}

Finding sum of digits of our number.

if (sum >= max_sum)
{
    max_sum = sum;
    max_prime = i;
}

If the sum is bigger than already we have found, we are setting this sum as biggest one and also setting this number as biggest prime number.

cout << max_prime;

Printing the biggest prime number.