โปรแกรม C++ เพื่อค้นหาจำนวนเต็มที่ใกล้เคียงที่สุดซึ่งตัวเลขและหลักผลรวม gcd มากกว่า 1

สมมติว่าเรามีตัวเลข N พิจารณาฟังก์ชัน gcdSum(x) ของจำนวนเต็มบวก x ซึ่งเป็น gcd ของจำนวนเต็มนั้นด้วยผลรวมของหลัก เราต้องหาจำนวนเต็มที่น้อยที่สุด x>=n เช่น gcdSum(x)> 1

ดังนั้น หากอินพุตเป็น N =31 เอาต์พุตจะเป็น 33 เนื่องจาก gcd ของ 31 และ (3+1) คือ 1 gcd ของ 32 และ (3+2) คือ 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;
}

อินพุต

31

ผลลัพธ์

33