在两个数字之间找到素数 gcd

Question

对于 c 语言的学生课程，我需要找到两个整数的素数最大公约数 (gcd)。如果没有答案，输出应该是 1。只能使用if语句、scanf、循环（不能使用外部函数）。

输入和输出示例：

(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 的示例，但是 none 我找到了主要 gcd。

Answer 1

修复示例

#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;
}

Answer 2

您可以直接使用：

第一步：生成所有小于最大 int 值的素数列表。

第二步：使用该列表和试除法找到每个给定整数的质因数。保留每个主要因素的列表。

第三步：检查一个因素列表，检查每个因素是否在另一个列表中。如果只有一个，那就是你最大的公约数。如果两个列表中都有多个，则 GCD 不是质数。

Answer 3

import java.util.Scanner;
public class Main
{
    static boolean CheckPrime(int n)
    {
        int flag=0;
        if(n==0 || n==1)
        {
            flag=0;
        }
        for(int i=2;i<=n/2;i++)
        {
            if(n%i==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
          return true;
        }
        else
        {
            return false;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1=sc.nextInt();
        int n2=sc.nextInt();
        int[] arr1 = new int[n1];
        int[] arr2 = new int[n2];
        for(int i=2;i<=n1;i++)
        {
            if(n1%i==0)
            {
                if(CheckPrime(i))
                {
                 arr1[i-2]=i;
                }
            }
        }
        for(int j=2;j<=n2;j++)
        {
            if(n2%j==0)
            {
                if(CheckPrime(j))
                {
                 arr2[j-2]=j;
                }
            }
        }
        int max=-1;
        for(int i=1;i<n1;i++)
        {
            for(int j=1;j<n2;j++)
            {
                if(arr1[i]==arr2[j])
                {
                    if(max<arr2[j])
                    {
                        max=arr2[j];
                    }
                    break;
                }
            }
        }
        if(max==0){max=1;}
        System.out.print(max);
    }
}

在两个数字之间找到素数 gcd

Find Prime gcd between two numbers

c

greatest-common-divisor