[JAVA] 프로그래머스 소수 찾기 | 에라토스테네스체 | 골든바흐의 추측

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- 2중 for문을 이용하여 간단하게 해결가능한 문제이지만 학습 겸 '에라토스테네스의 체' 개념을 사용하여 풀이했다.

- 소수를 찾으면 해당 수의 배수는 모두 소수가 아니다.

- boolean 배열을 n+2(0과 n 포함) 선언하여 소수를 만날 때마다 배수를 true 처리 한다.

- 배열에서 false의 인덱스가 소수이다.

 

 

 

파이썬으로 정리한 에라토스테네스의 체(골든바흐의 추측) 아래 글을 참고하세요!

 

2023.02.22 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 6588 골드바흐의 추측 | 시간 초과 | 에라토스테네스의 체 | 소수 구하기 끝판왕

 

 

작성 코드

에라토스테네스의 체

class Solution {
    public int solution(int n) {
        boolean[] tf = new boolean[n+2];
        int answer = 0;
        for(int i=2; i<n+1; i++){
            if(!tf[i]){
                answer++;
                for(int j=i*2; j<n+1; j+=i)
                    tf[j] = true;
            }
        }
        return answer;
    }
}

다른 풀이

import java.lang.Math;
class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2; i<n+1; i++){
            boolean flag = false;
            for(int j=2; j<=Math.sqrt(i); j++){  // i의 제곱근까지만 확인해도 됨
                if(i % j == 0){
                    flag = true;
                    break;
                }
            }
            if(!flag)
                answer++;
        }
        return answer;
    }
}

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚