[Programmers] Lv1. 소수 찾기 (feat. 에라토스테네스의 체)

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

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

 

코딩테스트 문제 풀이 과정

1. 문제를 파악한다.

2. 열심히 생각한다.

3. 코드로 쓴다.

 

이번 문제 풀이 Key Point

1. 소수에 대한 개념.

2. 단순히 for 문 여러번 돌리는 코드를 짜면 시간 테스트 통과 x.

3. 에라토스테네스의 체에 대해 알고있으면 문제 풀이가 더 수월함.

 

에라토스테네스의 체

import java.util.*;

public class Erastos {
    public static void main(String[] args){

    ArrayList<Boolean> primeList;

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();

    if(n<=1) return;

    primeList = new ArrayList<Boolean>(n+1);
    primeList.add(false);
    primeList.add(false);

    // 2 ~ n 까지 소수로 설정
    for(int i=0; i<=n; i++){
        primeList.add(i, true);
    }

    // 2 ~ i*i <=n
    for(int i=0; (i*i) <= n; i++){
        if(primeList.get(i)){
            // 각각의 배수들을 지운다
            for(int j=i*i; j<=n; j+=i){
                primeList.set(j, false);
            }
        }
    }

    StringBuffer sb = new StringBuffer();
    sb.append("{");

    for(int i=0; i<=n; i++){
        if(primeList.get(i) == true){
            sb.append(i);
            sb.append(",");
        }
    }
    sb.setCharAt(sb.length()-1, '}');

    System.out.println(sb.toString());

    }
}