[프로그래머스] level1. 소수 찾기 (자바 JAVA)

[ 문제 ]  [프로그래머스] level1. 소수 찾기 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12921

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

---

# 접근 방법 및 풀이 

 

• 처음에 원래 알고있는 소수 찾는 코드로 풀었는데 시간효율성 다 틀려서.. 띠용?
• 인터넷 보니까 어떤 숫자가 소수인지 확인할때 그 숫자를 2부터 해당 숫자의 제곱근범위까지로만 살펴보면 된다는 걸 깨달았다. "에라토스테네스의 체"를 이해한다면 쉽게 풀 수 있다.

# 주의할 점 

 

• 시간 효율성 문제가 있기때문에 에라토스테네스의 체를 이용해서 풀어야한다.

 

JAVA 코드

효율성 틀린 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        out: for(int i = 2; i <= n ; i ++){
            for(int j = 2; j <= i/j; j++){
                if(i%j == 0)
                    continue out;
            }
            answer++;
        }
        return answer;
    }
}

효율성 통과 코드

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        out: for(int i = 2; i <= n ; i ++){
            for(int j = 2; j <= Math.sqrt(i); j++){
                if(i%j == 0)
                    continue out;
            }
            answer++;
        }
        return answer;
    }
}

 

 

REVIEW

소수 찾을때 Math.sqrt(num) 범위로 해서 풀기!