숫자와 숫자의 합 gcd가 1보다 큰 가장 가까운 정수를 찾는 C++ 프로그램

<시간/>

숫자 N이 있다고 가정합니다. 자릿수 합과 함께 해당 정수의 gcd인 양의 정수 x의 함수 gcdSum(x)을 고려하십시오. gcdSum(x)> 1이 되도록 가장 작은 정수 x>=n을 찾아야 합니다.

따라서 입력이 N =31과 같으면 출력은 33이 됩니다. 왜냐하면 31과 (3+1)의 gcd는 1이기 때문입니다. 32와 (3+2)의 gcd는 1이고 gcd는 33과 ( 3+3)은 3입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}