Codility_CountFactors

functionMan·2024년 8월 29일

codility

Codility

목록 보기

28/32

10-1. CountFactors

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

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

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

양의 정수 D는 양의 정수 N의 인수입니다. 만약 정수 M이 존재하여 N = D * M을 만족한다면, D는 N의 인수입니다.

예를 들어, 6은 24의 인수입니다. 왜냐하면 M = 4가 위의 조건을 만족하기 때문입니다 (24 = 6 * 4).

다음과 같은 함수를 작성하세요:

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

이 함수는 양의 정수 N이 주어졌을 때, N의 인수의 수를 반환해야 합니다.

예를 들어, N = 24가 주어지면, 함수는 8을 반환해야 합니다. 왜냐하면 24는 8개의 인수(1, 2, 3, 4, 6, 8, 12, 24)를 가지고 있기 때문입니다. 24의 다른 인수는 없습니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

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

해당 코드로 제출 시 큰수에서 타임아웃 발생

수정 ->

import java.util.*;

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