[Kotlin] 백준 1978 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

 

풀이

소수를 찾는 효과적인 방법은 "에라토스테네스의 체"

 

에라토스테네스의 체 핵심은 "소수의 배수는 소수가 아니다" 이다.

 

1부터 최댓값(여기서는 1000)까지 미리 모든 소수를 구해놓는다.

1~N의 제곱근까지 두번의 반복문으로 최대 N까지 수행되며, O(N)의 시간복잡도를 가진다.

 

코틀린 풀이 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
	// 에라토스테네스의 체
    val max = 1000
    val N = readLine().toInt()	// 입력으로 주어지는 N 값
    val list = readLine().split(" ").map{ it.toInt() }	// 입력으로 주어지는 리스트
    val primeArray = BooleanArray(max + 1) { true }	// 0~1000까지 숫자가 소수인지 여부를 저장
    var result = 0	// 주어진 리스트 중 소수의 갯수
    
    // 초기값 세팅, 0과 1은 소수가 아님 예외처리
    primeArray[0] = false
    primeArray[1] = false
    
    // 2부터 최댓값(1000)의 루트 값까지 순환
    for(i in 2..Math.sqrt(max.toDouble()).toInt()) {
        // 현재 값이 소수라면 현재 값의 배수는 모두 소수가 아님
        if(primeArray[i]){
        	// 본인의 제곱부터 최댓값(1000)까지의 배수 처리
            // 본인보다 작은 값을 곱하는 케이스는 선행되었을 것이므로 수행하지 않음 (4x3의 경우, 3x4로 수행되었음)
            for(j in i * i..max step i) {
            	primeArray[ j ] = false                
            }
        }
    }
   
   	// 입력된 리스트를 순회하며 소수의 갯수를 확인 후 출력
    list.forEach{ if(primeArray[it]) result++ }
    println(result) 
}