查找兩個數字之間的素數gcd

對於c中的學生課程，我需要找到兩個整數的主要最大公約數（gcd）。如果沒有答案，輸出應該是1. 只能使用if語句，scanf，循環（無外部函數）。輸入和輸出查找兩個數字之間的素數gcd

例子：

(20,20)--->5 
(21,20)--->1 
(22,20)--->2 
(29,29)--->29

是否有人可以幫助我？這是我到目前爲止有：

#include <stdio.h> 
int main() 
{ 
    int num1, num2, i, hcf; 
    printf("Enter two integers: "); 
    scanf("%d %d", &num1, &num2); 
    for(i=1; i<=num1 || i<=num2; ++i) 
    { 
     if(num1%i==0 && num2%i==0) /* Checking whether i is a factor of both number */ 
      hcf=i; 
    } 
    printf("gcd of %d and %d is %d", num1, num2, hcf); 
    return 0; 
}

有關於如何發現我已經找到了黃金GCD的GCD，但沒有很多的例子。

來源

2015-11-07 Dart

你可以明顯地測試所有類似於篩選算法的素數。雖然這不會很有效。另一種選擇（有點類似）是找到一個數字的因素，並檢查是否分開另一個（抓住它們的最大值）。 –

修復

#include <stdio.h> 

int main(void){ 
    int num1, num2, i, hcf = 1; 
    int tmp1, tmp2; 
    printf("Enter two integers: "); 
    scanf("%d %d", &num1, &num2); 
    tmp1 = num1; 
    tmp2 = num2; 
    for(i=2; i<= tmp1 && i<= tmp2; ++i){ 
     while(tmp1 % i== 0 && tmp2 % i == 0){ 
      hcf=i; 
      tmp1 /= hcf; 
      tmp2 /= hcf; 
     } 
    } 
    printf("gcd of %d and %d is %d", num1, num2, hcf); 
    return 0; 
}

來源

2015-11-07 17:19:24 BLUEPIXY

（代碼|鏈接） - 唯一的答案是（與非常高尚的無意義的社區wiki一起）這個網站的恥辱...... – 3442

我認爲代碼是完整的描述。由於修正很小。 – BLUEPIXY

這也不能解決問題。 –

的樣品你可以做它的簡單的方法：

步驟一：生成所有素數小於最大int值的列表。

第二步：使用該列表和試劃，找出每個給定整數的主要因素。保留每個主要因素的列表。

第三步：查看一個因素列表，並檢查每個因素是否在另一個列表中。如果只有一個，那是你最大的普通素數除數。如果兩個列表中都有一個以上，那麼GCD不是主要的。

來源

2015-11-07 17:54:19

試着想想'（20,20）---> 5'。 – BLUEPIXY

非常感謝！這真的幫助了我 – Dart

查找兩個數字之間的素數gcd

回答

相關問題