에라토스테네스의 체

백준 2960 에레토스테네스의 체

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

static int N, K;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

N = sc.nextInt();

K = sc.nextInt();

boolean[] number = new boolean[N+1];

ArrayList<Integer> del = new ArrayList<>();

int count=0;

breakOut:

for(int start=2; start<=N; start++) {

if(number[start]==true) continue;

for(int i=1; start*i<=N; i++) {

if(number[start*i]==false) {

number[start*i] = true;

del.add(start*i);

if(K <= ++count) break breakOut;

}

}

}//for

System.out.println(del.get(K-1));

}

}

링크: http://marobiana.tistory.com/91

이건 루트n까지만 구하는 방법 못쓴다.

루트n까지만 하면 뒷부분은 안지우고 소수가 존재하는 앞부분만 체크하면 된다.

하지만 이문제는 지우는 거의 개수를 구하는 거라 전체적으로 다 지우는 연산을 해주어야 한다