[Codility] 第十課 Prime and composite numbers*

這次的題目略為簡單，但是還是要注意效率。

題目

如果存在整數 M 使得N = D * M，那麼正整數 D 是正整數 N 的因數，
舉例來說， 6 是 24 的因數，因為 M=4 滿足這個條件 (24 = 6*4)。

寫一個函數

class Solution { public int solution(int N); }

給一個 N=24，該函數應該返回 8 ，因為 24 有 8 個因數，分別是 1, 2, 3, 4, 6, 8, 12, 24

針對以下假設編寫有效的算法：

N是在[1..2,147,483,647]範圍內的整數。

Java 程式碼

class Solution {
    public int solution(int N) {
        int result = 0;
        for(int i = 1;i <= N;i++){
            if(N % i == 0){
                result ++;
            }
        }
        return result;
        
    }
}

分數共拿 71%，有效率問題所以有些測試資料 Timeout。
後來利用開根號減少 For 迴圈跑的次數。

Java 程式碼

class Solution {
    public int solution(int N) {
       int result = 0;
        for (int i=1; i<=Math.sqrt(N); i++) {
            if(i==Math.sqrt(N)) {
                result++;
            }else if(N % i == 0) {
                result = result + 2;
            }   

        }
        
        return result;
    }
}

分數共拿 100%，任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想



感謝相關連結
https://www.codility.com/
https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/