jayyhkwon의 개발공부로그

BOJ 2960번 소수(에레토스테네스의 체)

26 Dec 2019 | Algorithm

소수

  • 약수가 1과 자기 자신밖에 없는 수

  • N이 소수이면 N이 2<=x<N-1에 존재하는 x로 나누어 떨어지면 안된다.

  1. 어떤 수 N이 소수인지 아닌지 판별
public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i<n; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}

1-2. N이 소수가 아니다 -> N = 2 * N/2로 나타낼 수 있다.

  • -> N이 소수이려면 2<=x<=N/2에 존재하는 x로 나누어 떨어지면 안된다.
  • N = a * b로 나타낼 수 있으며 a의 최소값은 2이므로 b<=N/2이다.
public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i<=n/2; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}

1-3. N이 소수가 아니다 -> a<=√N, b>=√N (a<=b)

  • -> N이 소수이려면 2<=x<=√N에 존재하는 x로 나누어 떨어지면 안된다

  • 24인 경우 √24 = 4….이고 24의 약수는 1,2,3,4,6,12,24 이다.

  • √N 보다 작은 약수가 소수여야 √N보다 큰 약수와 곱하였을때도 소수이고 √N 보다 작은 원소의 갯수가 √N보다 큰 원소의 갯수보다 작으므로 √N 보다 작은 원소까지 검사한다

public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i*i<=n; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}
  1. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법
  • 에라토스테네스의 체
package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * BOJ 2960
 * https://www.acmicpc.net/problem/2960
 */
public class Eratosthenes_2960 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split("\\s");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);

        int answer = eratosthenes(new boolean[n+1],k);
        System.out.println(answer);
    }

    private static int eratosthenes(boolean[] input, int k){
        List<Integer> answer = new ArrayList<>();
        int cnt =0;
        for(int i=2; i<input.length; i++){
            if(input[i] == false) { // 안 지워진 경우
                answer.add(i);
            }
            for(int j=2*i; j<input.length; j+=i){ // j=i*i로 하면 stackoverflow 발생할 수 있다
                if(input[j] == false)
                    answer.add(j);
                input[j] = true; // 지워진 경우
            }
        }
        return answer.get(k-1);
    }
}

Related Posts