Đếm thừa số chung trong C++

Trong chủ đề này, chúng ta sẽ tìm hiểu về GCD và tìm ra các cách khác nhau để lấy GCD hai số trong ngôn ngữ lập trình C

GCD là một thuật ngữ toán học cho Ước chung lớn nhất của hai hoặc nhiều số. Ước chung lớn nhất chia hết cho hai hay nhiều số mà không dư. Do đó, nó còn được gọi là Thừa số chung lớn nhất (HCF) của hai số. Ví dụ: ƯCLN của hai số 20 và 28 là 4 vì cả 20 và 28 đều chia hết cho 1, 2, 4 (số dư là 0) và là số dương lớn nhất trong các thừa số 1, 2 và 4 . Tương tự ƯCLN của 2 số 24 và 60 là 12

GCD của hai số sử dụng vòng lặp for

Hãy xem xét một chương trình để lấy GCD của hai số trong C bằng vòng lặp for

Gcd_for. c

đầu ra

Enter any two numbers:
 96
36
 GCD of two numbers 96 and 36 is 12.

GCD của hai số sử dụng vòng lặp while

Hãy xem xét một chương trình để lấy GCD của hai số trong C bằng cách sử dụng vòng lặp while

Gcd_while. c

đầu ra

GCD of two numbers 50 and 60 is 10.

Nhận GCD của N số từ người dùng

Hãy xem xét một chương trình để lấy GCD gồm n số bằng cách lấy đầu vào từ người dùng

gcdNum. c

đầu ra

GCD of two numbers 50 and 60 is 10.

Nhận GCD của N số từ người dùng

Hãy xem xét một chương trình để lấy GCD gồm n số bằng cách lấy đầu vào từ người dùng

gcdNum. c

đầu ra

Enter the N numbers from the users ( 0 to exists from the loop)
196
224
48
96
36
256
0

 GCD of all entered number is: 4

Nhận GCD của hai số bằng chức năng do người dùng xác định

Hãy xem xét một chương trình để lấy GCD của hai số bằng hàm do người dùng xác định

chức năng. c

đầu ra

Enter the first number
96
 Enter the second number
 132
 GCD of the two numbers 96 and 132 is 12

GCD của hai số sử dụng toán tử modulo

Hãy xem xét một chương trình tìm GCD của hai số bằng toán tử modulo

mô-đun. c

đầu ra

Enter the first number:
 256
 Enter the second number:
 92
 GCD of two number 256 and 92 is 4

GCD của hai số sử dụng Đệ quy

Hãy xem xét một chương trình tìm GCD của hai số trong C bằng cách sử dụng Đệ quy

đệ quy. c

đầu ra

Enter any two positive numbers:
60
48
GCD of two numbers 60 and 48 is 12

Trong chương trình trên, hàm đệ quy GCD_Rec() liên tục gọi chính nó cho đến khi giá trị của num2 bằng 0

Đang được tính toán mỗi lần lặp lại. Nhưng nó bất biến vòng lặp. Nói chung, mã bất biến vòng lặp có thể được tính toán trước vòng lặp và được lưu trữ. Nó sẽ tăng lên, nhưng rõ ràng có nhiều cách tốt hơn để cải thiện mọi thứ. Tôi sẽ mô tả một cái dưới đây

bạn có thể làm điều này nhanh hơn nhiều bằng cách tính xem có bao nhiêu thừa số nguyên tố chung và bằng cách chia ra bất kỳ số nguyên tố "tìm được" nào khi bạn thực hiện. e. g. nếu chỉ có một số chia hết cho 5, còn số kia thì không, bạn có thể chia số đó cho 5 và bạn vẫn nhận được cùng một câu trả lời cho các thừa số chung. Chia m và n cho bất kỳ số "tìm thấy" nào khi bạn đi qua nó. (nhưng tiếp tục kiểm tra xem một trong hai có chia hết cho e không. g. 2 và tiếp tục chia trước khi bạn tiếp tục)

e. g. nếu hai số đều chia hết cho 2, 3 và 5 thì số cách kết hợp của ba số nguyên tố đó là 8 (2^3), coi sự có mặt của mỗi số nguyên tố là đúng/sai. Vì vậy, mỗi số nguyên tố xuất hiện một lần nhân số tổ hợp với 2

Nếu bất kỳ số nguyên tố nào xuất hiện nhiều lần, thì nó sẽ thay đổi phương trình một chút. e. g. nếu hai số chia hết cho 4, 3, 5

4 = 2^2, vì vậy bạn không thể có "2s", 1 "2" hoặc 2 "2s" trong hệ số kết hợp, vì vậy tổng số kết hợp 3 x 2 x 2 = 12. Vì vậy, bất kỳ số nguyên tố nào xuất hiện "x" lần, nhân tổng số tổ hợp với "x+1"

Vì vậy, về cơ bản, bạn không cần kiểm tra mọi thừa số thực tế, bạn chỉ cần tìm xem có bao nhiêu thừa số nguyên tố chung, sau đó tính xem có bao nhiêu tổ hợp cộng lại thành. May mắn thay, bạn chỉ cần lưu trữ một giá trị, "total_combos" và nhân nó với giá trị "x+1" cho mỗi số tìm thấy khi bạn thực hiện

Và một điều tiện lợi là bạn có thể chia tất cả các số nguyên tố khi chúng được tìm thấy và bạn được đảm bảo rằng số nguyên tố lớn nhất còn lại được tìm thấy không lớn hơn căn bậc hai của số nhỏ nhất còn lại trong số m và n

Vì vậy, để hướng dẫn bạn cách thức hoạt động của nó, hãy bắt đầu với một bản sao của m và n, lặp lại đến sqrt của phút tối thiểu của hai thứ đó (m và n sẽ bị giảm khi vòng lặp chạy qua)

tạo một giá trị "total_combos", bắt đầu từ 1

Kiểm tra số 2 trước, tìm xem có bao nhiêu lũy thừa chung của 2, thêm 1 vào số đó. Chia TẤT CẢ số 2 từ m và n, ngay cả khi chúng không khớp nhau, bởi vì việc giảm số lượng sẽ cắt giảm tổng số tiền bạn thực sự cần tìm kiếm. Bạn đếm số 2, thêm một, sau đó nhân "total_combos" với số đó. Tiếp tục chia m hoặc n cho 2 miễn là cả hai đều có thừa số là 2

Sau đó kiểm tra 3, tìm xem có bao nhiêu lũy thừa chung của 3, thêm một, nhân "total_combos" với số đó. Chia bất kỳ và tất cả các yếu tố của 3 khi bạn đang làm điều này

sau đó kiểm tra 4. Vì 4 không phải là số nguyên tố và chúng ta đã loại bỏ tất cả các số 2 nên sẽ không có số 4. Thêm một vào đó = 1, sau đó chúng ta nhân "total_combos" với 1, vì vậy nó giữ nguyên. Chúng tôi không cần kiểm tra xem 4 có phải là số nguyên tố hay không, các phép chia mà chúng tôi đã thực hiện đảm bảo nó bị bỏ qua. Tương tự cho mọi lũy thừa của 2

sau đó kiểm tra 5 giây. thỏa thuận tương tự như 2 và 3. Và như thế. Tất cả các cơ số nguyên tố được chia ra khi bạn đi, vì vậy, bất cứ khi nào một giá trị thực sự khớp với nhau, bạn có thể chắc chắn rằng đó là một số nguyên tố mới

dừng vòng lặp khi vượt quá sqrt(max(m,n)) (EDITED. min có lẽ sai ở đó). Nhưng m và n ở đây là các giá trị đã chia hết các số nguyên tố nhỏ hơn nên nó nhanh hơn nhiều

Làm thế nào để tìm các yếu tố chung trong c?

Làm thế nào để đếm các yếu tố của một số trong c?

Làm thế nào để có được HCF trong c?