[프로그래머스] 레벨1 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java 

코딩테스트 연습 - 소수 찾기

 

기존의 방법으로 구현해봤더니 계속 시간초과가 뜨는 것을 확인한 이후로 어떤 방법을 사용해야할지 고민해보았다. 구글링 끝에 '에라토스테네스의 체'라는 방식이 있는 것을 확인해서 해결했다.

중간에 continue 부분을 제외하고도 이 문제는 정답 처리가 되었는데 아마 극단적으로 n이 증가할 경우에는 내부 for문을 타지 않는 식으로 예외처리를 해줘야할 것 같다.

(에라토스테네스의 체, 소수판별)

 

 

class Solution 
{
    public int solution(int n) 
    {
        int cnt = 0;
        int[] arr = new int[n+1];
        
        for(int i=2; i<=n; i++)
        {
            arr[i] = i;
        }
        
        for(int i=2; i*i<=n; i++)
        {
            if(arr[i]==0)
            {
                continue;
            }
            for(int j=2*i; j<=n; j=j+i)
            {
                arr[j] = 0;
            }
        }
        
        for(int i=2; i<=n; i++)
        {
            if(arr[i]!=0)
            {
                cnt++;
            }
        }
        
        return cnt;
    }
}