[백준BOJ] 2960번 에라토스테네스의 체.java

 

백준 저지에서 팰린드롬수를 자바를 통해 풀어 보았다. 

 

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

2960번: 에라토스테네스의 체

2960번 에라토스테네스의 체.java

GitHub - tomy9729/TargetIsPlatinum5: 👯목표는 플레티넘5👯

 

 

1259번 팰린드롬수

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

설명

소수를 구하는 알고리즘 중 빠른 속도로 잘 알려진 에라토스테네스의 체이다. 문제 자체가 소수를 구하는 것은 아니지만 알고 있으면 매우 유용하다.

 

문제에 나와있는 순서 그대로 진행하면 된다. 

 

우선 N+1크기의 배열을 boolean 타입으로 선언하고 전부 true로 초기화했다. 배열이 true인 인덱스에 대해서만 문제에 나온 3번을 진행하고 그렇지 않다면 넘어간다. 

 

만약 삭제를 수행하면 해당 숫자를 인덱스로 하는 배열을 false로 초기화한다.

 

삭제를 수행할 때마다 count를 1씩 증가시키고 count가 K와 같은 때 인덱스를 출력한다.

코드

//2960번 에라토스테네스의 체.java
package week2;

import java.util.Arrays;
import java.util.Scanner;

public class 에라토스테네스의_체_2960 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		boolean isitprime[] = new boolean[N+1]; //삭제여부 확인 
		Arrays.fill(isitprime, true); //false면 삭제된 숫자
		
		int count=0;
		e : for(int i=2;i<=N;i++) { //2부터 시작
			if(isitprime[i]) { //삭제가 안된 숫자에 대해서
				int tmp=i;
				while(tmp<=N) { 
					if(isitprime[tmp]) {//삭제가 안되었을 때만 삭제
						isitprime[tmp]=false;
						count++;
						if(count==K) {
							System.out.println(tmp);//k번째로 삭제한 숫자면 출력
							break e;
						}
					}
					
					tmp += i;
				}
			}
		}
		
	}
}