---
# System prepended metadata

title: Java_Cmoney_st107
tags: [Cmoney_Java題目]

---

---
tags: Cmoney_Java題目
---
Java_Cmoney_st107
===

![](https://i.imgur.com/YaHtFFR.png)


1.需要的 function
---
1.1 找2數最大公因數(輾轉相除法)不用硬幹了!!!讚讚
---

```java=
public static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
```


1.2 判斷是否為質數
---

```java=
public static boolean prime(int a) {
    for (int i = 2; i < a; i++) {
        if (a % i == 0)
            return false;
    }
    return true;
}
```


1.3 質因數分解
---
1. 使用一個 for 迴圈(從2開始，因為1可以直接印"1^1"，到a結束，因為如果是質數，質因數分解只會有1和他自己)，創建一個 int 變數來計算，這個質因數可以除a幾次。
2. 使用一個 if 條件式(當是質數且是因數=質因數)。
3. 使用 while 迴圈(`a % i == 0`)一直除 a 來看要^多少，裡面記得`a/=i`，這樣迴圈才會結束。

```java=
public static void pf(int a) {
    System.out.print(a + "=1^1");
    for (int i = 2; i <= a; i++) {
        int count = 0;
        if (prime(i) && a % i == 0) {
            System.out.print("*" + i + "^");
            while (a % i == 0) {
                a /= i;
                count++;
            }
            System.out.print(count);
        }
    }
}
```


2.主程式
---
當只有一個數字的時候，gcd(0,n)會回傳n當作最大公因數，
前提是前面` int gcd = 0`。


題外話，之前嘗試在 for 迴圈的條件式裡面，這是個蠢主意，因為每個迴圈結束，就會再要求使用者輸入，別幹這種蠢事QQ。

```java=
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int gcd = 0;
        while (true) {
            int n = sc.nextInt();
            if (n == -1)
                break;
            gcd = gcd(gcd, n);
        }
        pf(gcd);
    }
```

3.完整程式
---
```java=
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int gcd = 0;
        while (true) {
            int n = sc.nextInt();
            if (n == -1)
                break;
            gcd = gcd(gcd, n);
        }
        pf(gcd);
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    public static void pf(int a) {
        System.out.print(a + "=1^1");
        for (int i = 2; i <= a; i++) {
            if (prime(i) && a % i == 0) {
                int count = 0;
                while (a % i == 0) {
                    a /= i;
                    count++;
                }
                System.out.print("*" + i + "^" + count);
            }
        }
    }

    public static boolean prime(int a) {
        for (int i = 2; i < a; i++) {
            if (a % i == 0)
                return false;
        }
        return true;
    }
}
```