查找两个数字之间的素数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

回答

相关问题