Common Factors (X, Y) and (Y, Z)

Find and print common factors of (X, Y) and (Y, Z) in descending order, allowing duplicates

Understand the Problem

Problem Statement

The program must accept three integers X, Y, Z as input. It must find all common factors of X and Y, then find all common factors of Y and Z. Finally, it must print all these factors in descending order, including duplicates if they appear in both sets.

For example, if the common factors of (X, Y) are [1, 2, 4] and the common factors of (Y, Z) are [1, 2, 4, 5, 10, 20], the output should be all factors from both lists in descending order.

Constraints

1 ≤ X, Y, Z ≤ 10⁶
All inputs are positive integers
The output should be printed in descending order
Common factors may appear twice in output if they are factors of both pairs

Examples

Example 1

Input

24 100 80

Output

20 10 5 4 4 2 2 1 1

Explanation

Common factors of (24, 100) are [1, 2, 4]. Common factors of (100, 80) are [1, 2, 4, 5, 10, 20]. When printed in descending order, we get: 20 10 5 4 4 2 2 1 1

Solution

#include <stdio.h>

int main() {
    int X, Y, Z;
    scanf("%d %d %d", &X, &Y, &Z);
    
    for (int i = Y; i >= 1; i--) {
        if (X % i == 0 && Y % i == 0) {
            printf("%d ", i);
        }
        if (Y % i == 0 && Z % i == 0) {
            printf("%d ", i);
        }
    }
    
    return 0;
}

Time:O(Y) - We iterate from Y down to 1

Space:O(1) - Only using a few integer variables

Approach:

1. Read three integers X, Y, Z using scanf.
2. Loop from Y down to 1 using variable i.
3. Check if i divides both X and Y (X % i == 0 && Y % i == 0). If true, print i.
4. Check if i divides both Y and Z (Y % i == 0 && Z % i == 0). If true, print i.
5. The loop naturally produces descending order output.

Visual Explanation

Loading diagram...

All Problems