Java 找出最大質數

思路：
1. 判斷一個數是否為質數
2. 找出一個範圍內所有質數
3. 找出質數中最大的數

一、判斷一個數是否為質數

寫一個方法，參數為數字，返回值為布林
true：是質數
false：非質數

質數的定義：
在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數

因此要判斷
1. 大於一
2. 二至該數減一的取餘不等於零

public boolean isPrime(int number) {
    if (number <= 1) {
        return false;
    }

    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

二、找出一個範圍內所有質數

使用迴圈+第一個方法即可
把質數裝進 List 中

public List<Integer> findPrime(int from, int to) {
    List<Integer> primes = new ArrayList<Integer>();
    for (int i = from; i <= to; i++) {
        if (isPrime(i)) {
            primes.add(i);
        }
    }
    return primes;
}

也可以寫一個 overload 方法

public List<Integer> findPrime(int to) {
    return findPrime(2, to);
}

三、找出最大質數

使用 findPrime() 取得質數 List
List 中最後一個數即是最大質數

有可能範圍內無質數的情況
因此要判斷後返回0

public int findLargestPrime(int from, int to) {
    List<Integer> primes = findPrime(from, to);
    if (primes.size() == 0) {
        return 0;
    }
    return primes.get(primes.size() - 1);
}

overload

public int findLargestPrime(int to) {
    return findLargestPrime(2, to);
}

測試

System.out.println(isPrime(-17)); //false
System.out.println(isPrime(1)); //false
System.out.println(isPrime(6)); //false
System.out.println(isPrime(11)); //true
System.out.println(findPrime(-20, 20)); //[2, 3, 5, 7, 11, 13, 17, 19]
System.out.println(findPrime(10)); //[2, 3, 5, 7]
System.out.println(findLargestPrime(-20, 20)); //19
System.out.println(findLargestPrime(10)); //7
System.out.println(findLargestPrime(3002, 3010)); //0

結論

雖然題目只要找出最大質數
但藉由拆解與設計
可以讓整支程式更清晰易讀
而且維護性、利用性也提高

例如又多了一個需求
要知道範圍內質數的數量
只要 list.size() 便完事

Tags: