Code Find the Greatest Common Prime Divisor

[nhaths4701 (Bùi Đức Nhật)]

Em code để giải bài toán này:

và code của em đây ạ:

#include<stdio.h>

int greatestCommonPrimeDivisor(int a, int b);
int check_prime(int num);
int main()
{
    int a, b;
    printf("Nhap a, b: ");
    scanf("%d" "%d",&a,&b);
    printf("\nKet qua la %d",greatestCommonPrimeDivisor(a,b));
}

int greatestCommonPrimeDivisor(int a, int b)
{
    int min, result = -1, fact = 1;
    if ((a<2)||(b<2)||(a>150)||(b>150))
    return result;
    else 
    {
        if (a >= b)
        min = b;
        else 
        min = a;

        for (int i=2;i<=min;++i)
        {
            if ((a%i==0)&&(b%i==0))
            {
                fact = check_prime(i);
                if (fact == 1)
                result = i;
            }
        }
        return result;
    }
}

int check_prime(int num) //Ham kiem tra co phai so nguyen to khong
{
    int count = 0;
    for (int i=2;i<=num/2;++i)
    {
        if (num%i == 0)
        {
            count ++;
            break;
        }
    }
    if (count)
    return 0;
    else 
    return 1;
}

Em test case trên codelearn chỉ được 7/8 case, mọi người chỉ lỗi giúp em với ạ! Tks mọi người!

[anon12276517]

Lỗi là timeout hay bị sai kết quả đó bạn ?

---

Nếu là timeout thì xem fix lại mấy vấn đề này:

for (int i=2;i<=num/2;++i)
{
    if (num%i == 0)
    {
        count ++;
        break;
    }
}

Chỉ cần chạy đến sqrt(num) là được. Và chỉ cần num % i == 0 thì return false luôn.

    for (int i=2;i<=min;++i)
    {
        if ((a%i==0)&&(b%i==0))
        {
            fact = check_prime(i);
            if (fact == 1)
            result = i;
        }
    }

Chỉ cần duyệt từ 2 ==> sqrt(min)

if(b % i == 0 && a % (b/i) == 0 && isPrime(b/i)) return b/i

Hoặc nhanh hơn nữa thì dùng sàng để lọc số nguyên tố từ 2 ==> min. Xong duyệt ngược để tìm i chia hết cho cả a b là được :))

---

Nếu sai kết quả thì check thử trường hợp a = b xem nó ra bao nhiêu ?? Hoặc đưa link bài để mình submit thử

[nhaths4701 (Bùi Đức Nhật)]

Cảm ơn bác nhiều, em thử làm luyện thuật toán ở codelearn ấy mà, link đây bác:

CodeLearn - Basic algorithms

Ở bài 3 Numberic ạ ^^.

[rogp10]

Nhanh nhất là chạy gcd(a, b) xong phân tích thừa số nguyên tố của nó

[anon12276517]

Bài này mình chạy sàng AC nhé :))