import java.util.*

fun mark_sieve(arr: BooleanArray, _first: Int, last: Int, factor: Int) {
    var first = _first;

    arr[first] = false

    while( last-first > factor ) {
        first += factor
        arr[first] = false;
    }
}


// 걸러내기 위한 인덱스들을 47페이지(한글판) 규칙에 따라 정리한 코드
fun sift0(first: Int, n: Int):BooleanArray {
    // n 크기 배열 생성 후 초기화
    var arr = BooleanArray(n)
    arr.fill(true)

    var i = 0
    var index_square = 3

    while (index_square < n) {
        // 고정: index_square = 2*i^2 + 6*i + 3
        if (arr[first+i]) {
            // this means arr[i] is a prime
            mark_sieve(arr, first + index_square, first + n, i + i + 3)
        }
        ++i
        index_square = 2*i*(i + 3) + 3
    }

    return arr
}

// 루프 안에서 mark_sieve를 호출 시 계산해야 하는 값들을 빼냄
fun sift1(first: Int, n: Int):BooleanArray {
    // n 크기 배열 생성 후 초기화
    var arr = BooleanArray(n)
    arr.fill(true)

    val last = first + n
    var i = 0
    var index_square = 3
    var factor = 3

    while (index_square < n) {
        // 고정: index_square = 2*i^2 + 6*i + 3
        // 고정: factor = 2i + 3
        if (arr[first+i]) {
            // this means arr[i] is a prime
            mark_sieve(arr, first + index_square, last, factor )
        }
        ++i
        factor = i + i + 3
        index_square = 2*i*(i + 3) + 3
    }

    return arr
}


// 우선순위 줄임(strength reduction) 기법을 통해 덜 비싼 연산을 사용하는 동등한 코드로 치환
// delta_factor = 2              : factor(i)는 초기값에서 시작해 2씩 증가하는 등차수열
// delta_index_square = factor(i) + factor(i+1)  : index_square는 factor(i)와 factor(i+1)을 더한 값
//
// 여기서 factor(i)는 이미 알고 있고(루프에서 새 factor를 계산하기 직전 값), factor(i+1)은 이번 루프에서 계산하면 된다.
fun sift2(first: Int, n: Int):BooleanArray {
    // n 크기 배열 생성 후 초기화
    var arr = BooleanArray(n)
    arr.fill(true)

    val last = first + n
    var i = 0
    var index_square = 3
    var factor = 3

    while (index_square < n) {
        // 고정: index_square = 2*i^2 + 6*i + 3
        // 고정: factor = 2i + 3
        if (arr[first+i]) {
            // this means arr[i] is a prime
            mark_sieve(arr, first + index_square, last, factor )
        }
        ++i
        index_square += factor        // factor를 계산하기 전에 index_square에 더해서 factor(i)를 추가
        factor += 2
        index_square += factor        // factor를 계산했으므로 현재 factor는 factor(i+1)을 저장하고 있음. 이를 index_square에 추가
    }
    return arr
}

fun testSameResults() {
    val arr0 = sift0(0, 100001)
    var arr1 = sift1(0, 100001)
    var arr2 = sift2(0, 100001)

    assert(Arrays.compare(arr0, arr1) == 0)
    assert(Arrays.compare(arr1, arr2) == 0)
    assert(Arrays.compare(arr2, arr0) == 0)
}

fun benchmark() {
    var sum1 = 0L
    var sum2 = 0L
    var sum3 = 0L
    (1..20).forEach {
        var t3 = System.nanoTime()
        sift0(0, 100000000)
        var t4 = System.nanoTime()
        sift1(0, 100000000)
        var t5 = System.nanoTime()
        sift2(0, 100000000)
        var t6 = System.nanoTime()

        sum1 += (t4 - t3)
        sum2 += (t5 - t4)
        sum3 += (t6 - t5)
        println("sift0: ${t4 - t3}")
        println("sift1: ${t5 - t4}")
        println("sift2: ${t6 - t5}")
    }

    println("average sift0 : ${sum1 / 20.0}")
    println("average sift1 : ${sum2 / 20.0}")
    println("average sift2 : ${sum3 / 20.0}")
}

// 내 컴퓨터에서(맥북프로 2017) : 단위 나노초
//
// average sift0 : 8.470951253E8
// average sift1 : 8.4314250685E8
// average sift2 : 8.4427361505E8/
//

var arr107 = sift2(0,107)

println(
    arr107.mapIndexed{i, b -> Pair(i*2+3, b)}
    .filter{it.second}
    .map{it.first}
    .joinToString(prefix="{ ", postfix = " }"))

// arr107에 있는 불린 데이터를 가지고
// (소수, 누적 소수 개수)로 이뤄진 컬렉션을 만든다
// 체를 걸러서 남은 소수 리스트에서 소수 누적 개수는 인덱스에 2를 더해야 한다.
// (짝수 소수 2가 리스트에서 빠져있고, 0번이 첫번째 홀수 소수이므로 누적은 2부터 시작이다)
var coords = arr107.mapIndexed{i, b -> Pair(i*2+3, b)}
    .filter{it.second}
    .map{it.first}
    .mapIndexed { index, i -> Pair(i, index+2) }

// 맨 앞에 짝수 소수인 2를 추가해준다
val all = listOf(Pair(2,1))+coords.toList()

// 그래프를 엑셀에서 쉽게 그리기 위해 소수와 소수 사이의 빈 (수, 누적개수) 쌍들을 채워넣어준다
// 일단 windowed(2)를 해서 인접한 두 (소수, 누적개수)의 쌍을 찾고,
// 인접 두 소수 사이의 수를 코틀린 .. (범위를 만들어내는 연산자)를 사용해 만들어내서 (수, 누적개수) 쌍 리스트를 만든다
// 이를 flatMap으로 펼쳐서 빈 정수 값이 없는 누적 분포를 만들어낸다
val full = all.windowed(2).flatMap {
    (first, second) -> (first.first .. (second.first-1)).map { Pair(it, first.second) }
}

// 엑셀에 사용하기 위해 ,로 분리하고 한 줄에 한 쌍만 표시한다
println(full.joinToString(separator = "\n", transform = { "${it.first}, ${it.second}" }))

fun gcm(a:Int, b:Int): Int =
    if(a==b) b
    else if(a > b) gcm(a-b, b)
    else /*if(a<b)*/ gcm(a, b-a)

println("gcm(196,42) = ${gcm(196,42)}")
println("gcm(154,42) = ${gcm(154,42)}")
println("gcm(112,42) = ${gcm(112,42)}")