[Java] - 소수 찾기 (12921)

📚 문제 - 12921

문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한사항

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

• 입출력 예 #1
  1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
• 입출력 예 #2
  1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
  
  

⌨️ 작성한 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        // 1은 소수 X
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) answer += 1;
        }
        return answer;
    }
    
    // 소수 판별 메서드
    private boolean isPrime(int num) {
    	// 2부터 num의 제곱근까지 반복
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
        	// i로 나눈 나머지가 0이면 소수 X
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

• 접근 방식:
  소수인지 판단하는 메소드를 만들어서, 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 for()문으로 구하면 될 것 같았다.
  
  
• 문제&해결:
  처음에는 소수만들기 문제에서 썼던 그래도 isPrime() 함수를 썼었는데 효율성 테스트에서 시간초과됐다. 그래서 반환 타입을 boolean으로 바꾸니 통과할 수 있었다.

  

  
  

👀 다른  사람의 풀이

class Solution {
    public int solution(int n) {
        boolean[] isPrime = new boolean[n + 1];
        int answer = 0;

        // 배열 초기화
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체 알고리즘
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 소수 개수 세기
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                answer += 1;
            }
        }
        return answer;
    }
}

 

✅ 배운 점

isPrime 배열을 사용한 에라토스테네스의 체 알고리즘은 isPrime 배열을 초기에 모든 수를 소수로 가정하고, 알고리즘을 통해 소수가 아닌 수를 걸러내는 방식으로 동작한다. 각 소수의 배수를 제외시켜 소수를 찾아내기 때문에, 중복된 계산을 피할 수 있고 효율적으로 소수를 찾을 수 있어, 더 효율적이고 빠르게 결과를 도출한다.

 

반면에, 나의 풀이는 배열을 사용하지 않고 각 숫자에 대해 직접 소수 여부를 확인하는 방식이라서 불필요한 반복 계산이 많이 발생하여 시간이 더 오래 걸린다. 앞으로 계산이 중복되지는 않는 지 생각하면서 문제 풀이에 접근해야한다는 점을 배웠다.