C++ program to find nearest integer for which the number and its digits sum gcd is greater than 1

Suppose we have a number N. Consider a function gcdSum(x) of a positive integer x which is the gcd of that integer with its sum of digits. We have to find the smallest integer x >= n, such that gcdSum(x) > 1.

So, if the input is like N = 31, then the output will be 33, because gcd of 31 and (3+1) is 1. The gcd of 32 and (3+2) is 1, and gcd of 33 and (3+3) is 3.

Steps

To solve this, we will follow these steps −

for initialize i := n, when i <= n + 2, update (increase i by 1), do:    jml := 0    x := i    while x > 0, do:       jml := jml + x mod 10       x := x / 10    if gcd of i and jml is not equal to 1, then:       return i return 0

Example

Let us see the following implementation to get better understanding −

#include <bits/stdc++.h> using namespace std; int solve(int n) {    for (long i = n; i <= n + 2; i++) {       long jml = 0;       long x = i;       while (x > 0) {          jml += x % 10;          x /= 10;       }       if (__gcd(i, jml) != 1) {          return i;       }    }    return 0; } int main() {    int N = 31;    cout << solve(N) << endl; }

Input

31

Output

33