소수 찾기

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2;i<=n;i++)
        {
            int cnt=0;
            for(int j=2;j<=i;j++)
            {
                if(i%j==0)
                {
                  cnt++;  
                }
            }
            if(cnt==1)
            {
                answer++;
            }

        }
        
        return answer;
    }
}

 

결과

시간초과가 발생했다.

 

cnt 2이상일때 넘겨줬더니 워스트케이스에서의 시간복잡도가 반정도 줄어들었다.

 

 

[2번째시도]

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2;i<=n;i++)
        {
            int cnt=0;
            if(i>10)
            {
                for(int j=2;j<10;j++)
                {
                    if(i%j==0)
                    {
                      cnt++;
                    }
                }
                if(cnt==0)
                {
                    answer++;
                }
            }
            else
            {
                for(int j=2;j<=i;j++)
                {
                    if(i%j==0)
                    {
                      cnt++;
                    }
                }
                if(cnt==1)
                {
                    answer++;
                }
            }        }        return answer;
    }
}

 

10이하일때는 나눠떨어지는 수가 1이면 카운트를 세줬고, 10이상일때는 나눠떨어지는수가 0이면 카운트를 세줬다.

 

10이상의 워스트케이스는 17 34 이런 소수들끼리의 문제가 있어서 실패가 떳다.

결국 에리스토체? 공부를 해야겠다.

 

그리고 듣기론 sqrt로 하는방법도 있다고 해서 그걸로해서 시간복잡도를 줄여서 넣어야겠다.

 

sqrt 로 해봤더니 효율성은 통과가 안된다 에라토스체? 그걸로 적용해봐야겠다.

[효율성 탈락 코드]

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean flag =false;
        for(int i=2;i<=n;i++)
        {
            flag = true;
            for(int j=2;j<=(int)Math.sqrt(i);j++)
            {
                if(i%j==0)
                {
                  flag = false;
                }
            }
            
            if(flag==true)
            {
                answer++;
            }

        }
        
        return answer;
    }
}

에라토스테네스 체로 경우 풀었다.

 

1. 2부터 n까지 입력한다.

2. 나누어 떨어지는 공배수들을 0으로 처리한다.

3. 0이 아닌부분만 카운트를 센다.

 

이것때문에 하루를 날렸다...ㅠㅠ 좋은하루 ㅠㅠ

 

class Solution {
    static public int solution(int n) {
        int answer = 0;

        int [] temp_answer = new int[n+2];
        for(int i=2;i<=n;i++)
        {
            temp_answer[i] = i;
        }

        for(int i=2;i<=n;i++)
        {
            for(int j=2;j<=i;j++)
            {
                if(i*j>n) break;
                temp_answer[i*j] = 0;

            }
        }

        for(int i=2;i<=n;i++)
        {
            if(temp_answer[i]!=0)
            {
                answer++;
            }
        }

        return answer;
    }
}