[알고리즘] 소수 구하기 알고리즘 (에라토스테네스의 체)

소수는 약수로 1과 자기자신만을 가지는 수이다. 

즉, 소수의 배수들은 전부 소수를 약수로 가지기 때문에, 소수가 아니다.

그러므로, 소수를 찾고 싶다면 범위내의 소수의 배수들을 전부 제거하는 방식으로 찾을 수 있다.

 

 

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

▶ 코틀린으로 구현한 1978번 문제

import java.util.*

fun main(args: Array<String>) = with(Scanner(System.`in`)) {
    val prime : Array<Boolean> = Array(1001) {true}
    var count = 0 // 소수의 개수
    // true = 소수, false = 소수가 아님
    prime[0] = false
    prime[1] = false // 0과 1은 소수가 아님

    for (i in 2..1000)
        if (prime[i])
            for (j in 2 * i..1000 step i) prime[j] = false
    // 소수의 배수들을 싹다 false 처리

    repeat(nextInt()){
        if (prime[nextInt()]) count++
    } // N의 개수만큼 반복하여 입력받고 그 수가 소수인지 판별

    println(count)

}