Cari pembahagi sepunya terbesar dalam julat tertentu

Masalah menyatakan bahawa kita perlu mencari GCD dalam julat tertentu. Kami akan mendapat dua integer positif x dan y dan dua integer p dan q dalam julat [p,q]. Kita perlu mencari GCD (pembahagi sepunya terbesar) bagi nombor x dan y yang berada dalam julat [p,q]. GCD, yang dikenali dalam matematik sebagai pembahagi sepunya terbesar, ialah integer positif terbesar yang membahagi dua integer positif yang diberikan. Integer yang diberikan tidak boleh sifar. Untuk mana-mana dua integer positif x dan y, ia dinyatakan sebagai gcd(x,y).

Sebagai contoh, kita mempunyai dua integer positif 6 dan 9. Pembahagi sepunya terbesar gcd(6,9) ialah 3 kerana ia adalah nombor terbesar yang membahagi dua nombor ini.

Tetapi dalam masalah ini, kita perlu mencari pembahagi sepunya terbesar bagi dua integer positif yang diberikan dalam julat yang ditentukan. Marilah kita memahami masalah ini melalui contoh. Kita akan diberi 4 nombor sebagai input x dan y untuk mencari gcd nombor ini dan dua nombor yang menunjukkan julat gcd iaitu [p,q].

Input: x=8, y=12, p=1, q=3

Output: 2

Penjelasan - Oleh kerana pembahagi sepunya terbesar bagi dua nombor x dan y yang diberi ialah 4. Tetapi 4 tidak berada dalam julat [1,3]. Pembahagi sepunya terbesar dalam julat [1,3] ialah 2, iaitu keluaran yang kami kehendaki.

Input: x=17, y=15, a=5, b=10

Output: -1

Penjelasan - Pembahagi sepunya terbesar bagi nombor 17 dan 15 ialah 1. Kerana 1 tidak berada dalam julat yang diberikan [5,10]. Apabila tiada pembahagi biasa dalam julat yang diberikan, kita perlu mencetak -1 sebagai output.

Algoritma

Algoritma yang kami gunakan untuk menyelesaikan masalah adalah sangat mudah dan berkaitan secara matematik. Pertama, kita akan mencari gcd (pembahagi sepunya terbesar) bagi nombor x dan y. Dalam C++, terdapat fungsi terbina dalam dipanggil gcd() yang mengembalikan pembahagi sepunya terbesar nombor sebagai output.

Tatabahasa

int divisor=gcd(x,y);

Kita juga boleh menggunakan kaedah algoritma Euclidean yang cekap untuk mencari gcd bagi dua nombor. Kedua-duanya berfungsi pada masa yang sama dan kerumitan masa ialah O(log(min(x,y)).

Kini, kita boleh menggunakan hukum aritmetik mudah untuk membuat kesimpulan bahawa nombor yang membahagi gcd dua nombor juga akan dibahagikan dengan dua nombor itu sendiri . Jadi, lelaran daripada i=1 kepada sqrt(gcd(x,y)) dalam gelung for akan membantu kita mendapatkan semua pembahagi sepunya nombor itu.

Kemudian, semak sama ada setiap i hingga sqrt(gcd(x,y)) i membahagikan gcd(x,y). Jika saya membahagikan gcd(x,y), maka kita boleh mengatakan bahawa gcd(x,y)/i juga akan menjadi pembahagi gcd, dengan itu membuat kesimpulan bahawa ia juga merupakan pembahagi sepunya bagi nombor x dan y.

Mari kita memahami konsep ini melalui contoh. Katakan x dan y ialah 32 dan 48 masing-masing. gcd(18,27) ialah 16. Jadi dalam kes ini, kita akan lelaran daripada i=1 kepada i<=4, iaitu sqrt(16). Mari kita pertimbangkan i=2. Di sini saya bahagikan dengan gcd(18,27), iaitu 16/2, yang bersamaan dengan 8. Jadi gcd(x,y)/i juga membahagikan gcd(x,y) untuk mendapatkan i. <=4，即 sqrt(16)。让我们考虑 i=2。这里我除以 gcd(18,27)，即 16/2，等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。

Nota - Jika nombor n dibahagikan dengan sebarang nombor x untuk mendapatkan y, yang boleh dinyatakan sebagai $frac{n}{x}:=:y$ maka y akan membahagi n dengan x $(x:times: y:=: n)$.

Algoritma ini mungkin merupakan cara yang paling berkesan untuk menyelesaikan masalah ini. Semasa mengikuti algoritma ini, kami akan sentiasa menyemak sama ada penyebut biasa berada dalam julat [a,b]. Jika tidak, kami akan menggunakan fungsi max() untuk mengemas kini pembahagi dalam pembolehubah secara berterusan untuk mendapatkan pembahagi sepunya terbesar dalam julat.

sintaks fungsi maks()

int m = max(a,b);

Ia mengembalikan nilai maksimum a dan b.

Kaedah

Berikut adalah pendekatan yang akan kami ikuti -

• Mulakan fungsi untuk mengira pembahagi sepunya terbesar dalam julat tertentu.

• Hitung gcd bagi dua nombor positif x dan y yang diberi.

• Mulakan nama pembolehubah ans = -1.

• Lelaran daripada i=1 kepada i<=sqrt(gcd(x,y)) dalam gelung for dan terus semak sama ada saya membahagikan gcd(x,y). <=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。

• Jika (gcd(x,y)%i)=0, semak sama ada i berada dalam julat [a,b] dan gunakan fungsi max() untuk menyimpannya dalam ans supaya kita mendapat pembahagi sepunya terbesar yang terletak di dalam julat.

• Semak juga sama ada gcd/i berada dalam julat Jika ia berada dalam julat, gunakan fungsi max() sekali lagi untuk mengemas kini nilai ans.

• Kembalikan jawapan selepas melengkapkan semua lelaran dalam gelung untuk.

Contoh

Pelaksanaan kaedah ini dalam C++ -

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
   if(a == 0)
   return b;
   return gcd(b % a, a);
}

//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {

   //using C++ inbuilt library to calculate gcd of given numbers
   int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
   int ans = -1; //storing -1 for the case when no common divisor lies in the range
   for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
      //of a number must be less than square root of the number
      if(z % i == 0) {
         if(i >= a && i <= b) //checking it i lies in the range
         ans = max(ans, i); //storing maximum value
         if((z / i) >= a && (z / i) <= b)
         ans = max(ans, z / i);
      }
   }
   return ans;
}
int main() {
   int x, y, a, b;
   x=24, y=42, a=3, b=9;
   cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
   return 0;
}

Output

6 is the gcd that lies in range [3,9]

Kerumitan masa: O(log(min(x,y)) + sqrt(z)), di mana z ialah pembahagi sepunya terbesar bagi dua nombor x dan y.

Kerumitan ruang: O(1), kerana tiada ruang tambahan digunakan.

Kesimpulan

Kami membincangkan cara untuk menyelesaikan masalah gcd bagi dua nombor dalam julat [a,b]. Inilah cara kita boleh menyelesaikan masalah di atas dalam C++ menggunakan pelbagai fungsi yang berbeza.

Saya harap anda mendapati artikel ini membantu dan menjelaskan semua konsep anda yang berkaitan dengan isu ini.

Atas ialah kandungan terperinci Cari pembahagi sepunya terbesar dalam julat tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!