에라토스테네스의 체
백준 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까지만 하면 뒷부분은 안지우고 소수가 존재하는 앞부분만 체크하면 된다.
하지만 이문제는 지우는 거의 개수를 구하는 거라 전체적으로 다 지우는 연산을 해주어야 한다