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

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

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

---

Think🤔

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

계속해서 반복문을 두개 돌아서 숫자가 엄청 커졌을 때, 시간 초과가 뜬다.

 

1. 처음 방법, 전체를 돌리면서 전체 돌리는 숫자가 소수인지 판별하기 위해서 나눠서 1이상이면 소수라고 판별
==== > 해당방법 시간 초과
2. 두번째 방법으로 제곱근 까지만 반복문을 돌린다 어차피 자연수 n이 소수이기 위한 조건은 n의 제곱근 보다
작은 소수로도 나눠지지 않는 방법을 생각한다.
3. 세번째 방법 에라토스테네스의 체 
전체 갯수가 120이면 2의 배수를 다지운다 3의 배수를 다 지운다 5의 배수를 다 지운다 7의 배수를 다 지우면
모든 소수의 배수를 다 지우기 때문에 이러면 남는 수는 소수밖에 없다.

---

Solution✍

import java.util.*;

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

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
        arr[0] = 0; arr[1] = 0;
        
        // 각 자리 수를 배열에다가 저장시킴
        for(int i=2; i<=n; i++){
            arr[i] = i;
        }
        
        for(int i=2; i<=n; i++){
            if(arr[i] == 0){ // 만약 0이면 건너뛴다.
                continue;
            }
            //j는 자기 자신의 값을 더해서 배수를 빼준다
            for(int j=2*i; j<=n; j=j+i){ 
                arr[j] = 0;
            }
        }
        
        // 반복문을 이용해서 0이 아닌 값을 찾는다.
        for(int i=0; i<=n; i++){
            if(arr[i] != 0){
                answer++;
            }
        }
        
        return answer;
    }
}

---

Review🤩

배열을 이용해서 새롭게 풀 수 있었다.

---