Java 백준 1342 행운의 문자열

백준 링크

https://www.acmicpc.net/problem/15965

15965번: K번째 소수

---

문제

입력

출력

입출력 예시

서브 태스크

 

---

제출한 코드

import java.io.*;
import java.util.*;

import javax.swing.plaf.synth.SynthOptionPaneUI;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static ArrayList<Integer> data = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		int K = Integer.parseInt(br.readLine());
		findPrimes(K);
		System.out.println(data.get(K - 1));
	}

	static void findPrimes(int K) {
		// 1번째 소수 2
		data.add(2);
		int num = 3;
		while (data.size() < K) {
			boolean isPrime = true;
			// 기존에 저장된 소수들과 비교
			for (int prime : data) {
				if (prime * prime > num)
					break;
				// 소수의 배수인지 확인하기 위한 조건
				if (num % prime == 0) {
					isPrime = false;
					break;
				}
			}
			// 소수인 경우 data에 추가
			if (isPrime)
				data.add(num);
			// 2의 배수는 항상 소수가 아니기에 홀수만 확인한다.
			num += 2;
		}
	}
}

 

에라토스테네스의 해를 이용하는 문제이다.

 

1. 짝수는 다 2로 나누어지기에 소수에서 제외하기 위해 data에 2를 넣어주고 시작한다.

2. while문을 통해서 원하는 개수를 찾아준다.

3. 종료 조건으로 기존 소수의 배수인 경우와 데이터의 제곱이 현재 순회하는 값보다 크면 break;

4. 순회를 하면서 num는 짝수를 제외하기에 3부터 시작해서 2씩 증가시켜준다.