Kotlin에서의 에라스토테네스의 체 구현

소수 만들기

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수

nums result
[1,2,3,4] 1
[1,2,7,6,4] 4

에라스토테네스의 체

	var sosu = Array<Boolean>(3001) { i -> true }
    // 0과 1은 소수가 아님 false
    sosu[0] = false
    sosu[1] = false

    for(i in 2 until sosu.size){
    	// 소수가 아니면 pass
        if(!sosu[i]) continue
        
        // 자신의 배수인 수들에 모두 false
        var j = i*2
        while(j < sosu.size){
            sosu[j] = false
            j+=i
        }
    }
    
    println(sosu.contentToString())
// [false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, ....
//    0       1     2     3    4      5     6       7  .....
	

    
    var ans = 0
    for(i in 0 until nums.size){
        for(j in i+1 until nums.size){
            for(k in j+1 until nums.size){
               if(sosu[nums[i]+nums[j]+nums[k]]) {
                   ans+=1
               }
            }
        }
    }
    return ans