[프로그래머스][Lv.1][Java] 소수 찾기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

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

풀이

에라토스테니스의 체를 사용하면 된다. 

에라토스테니스의 체란?
→ 어떤 수의 배수는 소수가 아니므로 범위 내에서 소수가 아닌 수를 제외하는 방식

즉, 2의 배수부터 √n 까지의 제곱으로 나누어 떨어지는지 확인하면 된다.

코드1

import java.util.*;

class Solution {
    public int solution(int n) {
        int[] array = new int[n + 1];
        
        for (int i = 2; i <= n; i++) {
            array[i] = 1;
        }
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (array[i] == 0) continue;
            
            int num = i * 2;
            while (num <= n) {
                array[num] = 0;
                num += i;
            }
        }
        
        return Arrays.stream(array).sum();
    }
}

코드2

import java.util.*;

class Solution {
    public int solution(int n) {
        int[] array = new int[n + 1];
        int count = 0;
        
        for (int i = 2; i <= n; i++) {
            array[i] = 1;
        }
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (array[i] == 0) continue;
            
            int num = i * 2;
            while (num <= n) {
                array[num] = 0;
                num += i;
            }
        }
        
        for (int i = 2; i <= n; i++) {
            if (array[i] == 1) {
                count++;
            }
        }
        
        return count;
    }
}

코드1은 stream을 사용해서 코드를 간결하게 할 수 있었지만 코드2보다 속도가 느렸다.