Rumah >pembangunan bahagian belakang >C++ >Menyemak sama ada dua nombor yang diberikan adalah pasangan mesra
Nombor Mesra − Mengikut teori nombor, nombor mesra ialah dua atau lebih nombor dengan indeks kelimpahan yang sama.
Indeks Kekayaan - Indeks kekayaan nombor asli boleh ditakrifkan sebagai nisbah antara jumlah semua pembahagi nombor asli dan nombor asli itu sendiri.
Kelimpahan nombor n boleh dinyatakan sebagai $mathrm{frac{sigma(n)}{n}}$, dengan $mathrm{sigma(n)}$ mewakili fungsi pembahagi yang sama dengan semua pembahagi n.
Sebagai contoh, indeks kelimpahan nombor asli 30 ialah,
$$mathrm{frac{sigma(30)}{30}=frac{1+2+3+5+6+10+15+30}{30}=frac{72}{ 30}=frac{12} {5}}$$
Jika ada nombor m mn, maka nombor n itu dipanggil "nombor mesra".
$mathrm{frac{sigma(m)}{m}=frac{sigma(n)}{n}}$
Pasangan Mesra − Dua nombor dengan indeks lebihan yang sama dipanggil "pasangan mesra".
Diberi dua nombor Num1 dan Num2. Mengembalikan jika dua nombor bukan pasangan yang mesra.
Input: Num1 = 30, Num2 = 140
Output: YesTerjemahan bahasa Cina bagi
$$mathrm{frac{sigma(30)}{30}=frac{1+2+3+5+6+10+15+30}{30}=frac{72}{ 30}=frac{12} {5}}$$
$$mathrm{frac{sigma(140)}{140}=frac{1+2+4+5+7+10+14+20+28+35+70+140}{140 }=frac{336} {140}=frac{12}{5}}$$
Memandangkan, frac{sigma(30)}{30}=frac{sigma(140)}{140}, 30 dan 140 ialah pasangan nombor mesra.
Input: Num1 = 5, Num2 = 24
Output: NoTerjemahan bahasa Cina bagi
$$mathrm{frac{sigma(5)}{5}=frac{1+5}{5}=frac{6}{5}=frac{6}{5}} $$
$$mathrm{frac{sigma(24)}{24}=frac{1+2+3+4+6+8+12+24}{24}=frac{60}{ 24}=frac{15} {6}}$$
Memandangkan $mathrm{frac{sigma(5)}{5}neqfrac{sigma(24)}{24}}$, 5 dan 24 bukan pasangan mesra. p>
Cara brute force untuk menyelesaikan masalah ini adalah dengan terlebih dahulu mencari jumlah semua pembahagi dua nombor, kemudian mengira nilai indeks kelimpahannya, dan bandingkan untuk mendapatkan hasilnya.
procedure sumOfDivisors (n) sum = 0 for i = 1 to n if i is a factor of n sum = sum + i end if ans = sum end procedure procedure friendlyPair (num1, num2) sum1 = sumOfDivisors (num1) sum2 = sumOfDivisors (num2) abIndex1 = sum1 / num1 abIndex2 = sum2 / num2 if (abIndex1 == abIndex2) ans = TRUE else ans = FALSE end if end procedure
Dalam program di bawah, jumlah semua pembahagi dikira untuk mencari indeks kelimpahan.
#include <bits/stdc++.h> using namespace std; // Function to find sum of all the divisors of number n int sumOfDivisors(int n){ int sum = 0; for (int i = 1; i <= n; i++){ if (n % i == 0){ sum += i; } } return sum; } // Function to find if two numbers are friendly pairs or not int friendlyPair(int num1, int num2){ // Finding the sum of all divisors of num1 and num2 int sum1 = sumOfDivisors(num1); int sum2 = sumOfDivisors(num2); // Calculating the abundancy index as the ratio of the sum of divisors by the number int abIn1 = sum1 / num1, abIn2 = sum2 / num2; // Friendly pair if the abundancy index of both the numbers are same if (abIn1 == abIn2){ return true; } return false; } int main(){ int num1 = 30, num2 = 140; cout << num1 << " and " << num2 << " are friendly pair : "; if (friendlyPair(num1, num2)){ cout << "YES"; } else{ cout << "NO"; } return 0; }
30 and 140 are friendly pair : YES
Kerumitan masa - O(n) kerana fungsi sumOfDivisors() merentasi gelung
Kerumitan ruang - O(1)
Bentuk ringkas indeks kekayaan boleh didapati dengan membahagikan kedua-dua pengangka dan penyebut dengan pembahagi sepunya terbesar. Kami kemudian menyemak sama ada kedua-dua nombor itu adalah pasangan mesra dengan menyemak sama ada bentuk kekayaan yang dikurangkan adalah sama, iaitu menyemak sama ada pengangka dan penyebutnya adalah sama.
procedure sumOfDivisors (n) ans = 1 for i = 1 to sqrt(n) count = 0 sum = 1 term = 1 while n % i == 0 count = count + 1 n = n / i term = term * i sum = sum + term ans = ans * sum if n >= 2 ans = ans * (n + 1) end if end procedure procedure gcd (n1, n2) if n1 == 0 return n2 end if rem = n2 % n1 return gcd (rem, n2) end procedure procedure friendlyPair (num1, num2) sum1 = sumOfDivisors (num1) sum2 = sumOfDivisors (num2) gcd1 = gcd (num1, sum1) gcd2 = gcd (num2, sum2) if (num1 / gcd1 == num2 / gcd2) && (sum1 / gcd1 == sum2 / gcd2) ans = TRUE else ans = FALSE end if end procedure
Dalam atur cara di bawah, kami menyemak sama ada indeks kelimpahan bentuk terkurang dua nombor adalah sama dengan membandingkan pengangka dan penyebut.
#include <bits/stdc++.h> using namespace std; // Function to find the sum of all the divisors of number n int sumOfDivisors(int n){ int ans = 1; // By looping till sqrt(n), we traverse all the prime factors of n for (int i = 2; i <= sqrt(n); i++){ int cnt = 0, sum = 1, term = 1; while (n % i == 0){ cnt++; // Reducing the value of n n /= i; term *= i; sum += term; } ans *= sum; } // When n is a prime number greater than 2 if (n >= 2){ ans *= (n + 1); } return ans; } // Function to find the gcd of two numbers int gcd(int num1, int num2){ if (num1 == 0) { return num2; } int rem = num2 % num1; return gcd(rem, num1); } // Function to find if two numbers are friendly pairs or not int friendlyPair(int num1, int num2){ // Finding the sum of all divisors of num1 and num2 int sum1 = sumOfDivisors(num1); int sum2 = sumOfDivisors(num2); // Finding gcd of num and the sum of its divisors int gcd1 = gcd(num1, sum1); int gcd2 = gcd(num2, sum2); // Checking if the numerator and denominator of the reduced abundancy index are the same or not if (((num1 / gcd1) == (num2 / gcd2)) && ((sum1 / gcd1) == (sum2 / gcd2))){ return true; } return false; } int main(){ int num1 = 30, num2 = 140; cout << num1 << " and " << num2 << " are friendly pair : "; if (friendlyPair(num1, num2)){ cout << "YES"; } else{ cout << "NO"; } return 0; }
30 and 140 are friendly pair : YES
Kerumitan masa - Kerumitan masa bagi fungsi sumOfDivisors() ialah O(n1/2log2n).
Kerumitan ruang - O(1)
Ringkasnya, pasangan mesra merujuk kepada dua nombor asli dengan indeks kelimpahan yang sama, iaitu nisbah hasil tambah semua pembahagi nombor kepada nombor itu sendiri. Untuk mengetahui sama ada dua nombor ialah pasangan mesra, ikut pendekatan di atas, nyatakan penyelesaian brute-force dengan kerumitan masa O(n) dan penyelesaian yang dioptimumkan dengan kerumitan masa O(n1/2log2n).
Atas ialah kandungan terperinci Menyemak sama ada dua nombor yang diberikan adalah pasangan mesra. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!