[프로그래머스/Java] 12921번 :: Lv1. 소수 찾기

| 문제

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

프로그래머스

 

| 풀이

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

 

| 정리

2부터 i까지 나누는 방식으로 풀이하면 시간 초과가 나온다.

소수는 해당 수의 제곱근보다 작은 수들이기 때문에 반복문의 범위를 sqrt(i)로 좁혀서 풀이한다.