Chương trình C ++ để tìm số nguyên gần nhất mà số và các chữ số của nó tổng gcd lớn hơn 1

Giả sử chúng ta có một số N. Xét một hàm gcdSum (x) của một số nguyên dương x là gcd của số nguyên đó với tổng các chữ số của nó. Chúng ta phải tìm số nguyên nhỏ nhất x> =n, sao cho gcdSum (x)> 1.

Vì vậy, nếu đầu vào là N =31, thì đầu ra sẽ là 33, vì gcd của 31 và (3 + 1) là 1. Gcd của 32 và (3 + 2) là 1 và gcd của 33 và ( 3 + 3) là 3.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

31

Đầu ra

33