알고리즘 스터디 - 3주차 3

15965

• 알고리즘 : 아리토스테네스의 체
• 난이도 : 실버2

문제

15965

접근

• 소수란? 2이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때
• K번째의 소수를 구하기
  • K의 최대 수 500000
  • 최소 500000 크기의 배열이 필요함

가정

• 에라토스테네스의 체를 통해 소수를 구하면 될 것 같습니다.

풀어보기

package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) 	{
			Scanner scanner = new Scanner(System.in);
			int k = scanner.nextInt();
			boolean[] isPrime = eratosthenesChe();
			List<Integer> primes = new ArrayList<>();
			for(int i = 0; i<isPrime.length; i++){
				if(isPrime[i]){
					primes.add(i);
				}
			}
		System.out.println(primes.get(k-1));
	}
	public static boolean[] eratosthenesChe(){
		boolean[] isPrime = new boolean[10000001];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
		for(int p = 2; p * p <= 10000000; p++){
			if(isPrime[p]){
				for(int j = p * p; j <= 10000000; j += p){
					isPrime[j] = false;
				}
			}
		}

		return isPrime;
	}
}

시행착오

• 배열의 크기를 500000으로 잡아서 500000번째 소수를 찾지 못하였습니다.
• Long 타입으로 적용해야 되는 지 알고 잘 못 적용하였습니다.
• 500000번째 K의 수가 들어있을 배열의 위치를 찾는 것이 중요했습니다.

참고자료

• 에라토스테네스의 체