4
1 3 5 7

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) 
}

1. 문제

3. 풀이 (생각의 흐름)

1. 구간의 합 -> 3~7 구간의 합이란, 7까지 누적된 합 - 2까지 누적된 합과 동일하다

2. 3~7구간의 합 = 7 누적 합 - 2 누적 합

3. 누적 합이란 0부터 N까지 순차적으로 순회하면서 적용할 수 있다. -> Big O(N), N의 최대 값은 1,000이므로 수용한다.

4. 제출 소스

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val (s, e) = readLine().split(" ").map{ it.toInt() }	// 입력된 두 값을 받기 
    var n = 1	// 현재 구간의 값
    var c = 1	// 현재 구간의 값이 나온 횟수
    
    val arr = IntArray(e + 1)	// 구간의 누적합을 담을 배열
    arr[0] = 0					// 1구간을 index 1로 사용하므로 0구간의 합은 0

	// 구간 1부터 e까지 순회
    for (i : Int in 1..e){
        arr[i] = arr[i-1] + n	// 현재 구간의 누적합 = 이전 구간의 누적합 + 현재 구간의 값
        c++						// 현재 구간의 값이 나온 횟수를 추가
        if(c > n){				// 현재 구간의 값이 나온 횟수가 현재 구간의 값을 초과하다면, 값을 올리고 갯수를 1로 초기화
            n++
            c = 1
        }
    }
    
    println(arr[e] - arr[s-1])	// 출력: 끝 누적합 - 시작 지점 앞의 누적합
}