# 실전 줄리아 첫걸음

주어진 문제의 힌트와 조건을 보고 지시하는 코드를 작성하라. 톡방에 답안을 제출하면 예시 답안을 받을 수 있고, 오프라인 스터디까지 예시 답안과 본인 답안을 비교하는 코드리뷰를 준비하라.

<img src="https://i.imgur.com/bvNMs9L.png" width="200"> https://open.kakao.com/o/gIr6GsOd

## 1. 함수

### 힌트 1: 재귀함수

> 자기 자신을 호출하는 함수. 재귀 함수의 'recursive'는 ‘반복되는’이라는 의미를 갖고 있습니다. 프로그래밍에서 재귀 함수는 어떤 일을 하는 함수를 만들었을 때, 그 함수 안에서 자기 자신을 다시 불러서 함수가 실행되도록 만든 것입니다.

function pow2(n)
    if n ≤ 0
        return 1
    else
        return 2 * pow2(n-1)
    end
end

위의 `pow2` 함수는 2의 `n`승을 리턴하는 것을 재귀함수로 구현한 것이다.[^1] 그 실행결과는 다음과 같다:

[^1]: https://docs.julialang.org/en/v1/manual/functions/

julia> pow2(0)
1

julia> pow2(1)
2

julia> pow2(2)
4

### 힌트 2: 삼항연산자

> 컴퓨터 프로그래밍에서 ?:는 몇몇 프로그래밍 언어들에서 기본적인 조건식을 위한 문법의 일부이다. 이는 일반적으로 조건 연산자, 인라인 조건문(inline if), 또는 삼항 조건문(ternary if)으로 불린다. a ? b : c는, a가 참이면 b로 평가되고, 그 밖에는 c로 평가된다.

julia> isless6(n) = (n < 6 ? 1 : 0)
isless6 (generic function with 1 method)

julia> isless6(3)
1

julia> isless6(6)
0

julia> isless6(9)
0

위의 `isless6` 함수는 `n`이 6보다 작은지 판별하는 함수다.[^2]

[^2]: https://docs.julialang.org/en/v1/manual/control-flow/#man-conditional-evaluation

### 1-1 기본과제

힌트 1을 참고해 주어진 자연수 `n` 에 대해 $n$ 번째 피보나치 수 $F_n$ 을 리턴하는 함수 `F(n)` 을 작성하라. 단, $F_1 = F_2 = 1$ 이다.

### 1-2 심화과제

힌트 2를 참고해 함수 `F`와 같은 기능을 하는 함수 `F1`을 단 한 줄로 구현하라.

---

## 2. 자료구조

### 힌트 1: `push!()`

<iframe width="560" height="315" src="https://www.youtube.com/embed/NFETSCJON2M" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

julia> x = []
Any[]

julia> push!(x, 1)
1-element Vector{Any}:
 1

julia> push!(x, 1)
2-element Vector{Any}:
 1
 1

julia> push!(x, 2);

julia> push!(x, 3);

julia> push!(x, 5)
5-element Vector{Any}:
 1
 1
 2
 3
 5

### 힌트 2: `@time`

julia> @time F1(40)
  0.338643 seconds
102334155

`@time` 매크로를 통해 코드의 특정 블럭에서 소요된 시간을 계산할 수 있다. 함수의 앞에 쓰이면 간단하게 그 함수의 평가에 쓰인 시간을 볼 수 있다. [^3]

[^3]: https://docs.julialang.org/en/v1/manual/performance-tips/#Measure-performance-with-[@time](@ref)-and-pay-attention-to-memory-allocation

### 2-1 기본과제

`push!()`는 배열의 가장 마지막 자리에 주어진 원소를 추가하는 기능을 한다. 과제 1에서 구현한 `F` 혹은 `F1` 을 사용해서 자연수 `n`을 받아 $\left\{ F_k \right\}_{k=1}^{n}$ 을 반환하는 함수 `FA(n)`을 작성하라.

### 2-2 심화과제

> **동적 프로그래밍**이란, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

`FA(n)`과 기능이 같지만 동적 프로그래밍을 응용하여 속도를 개선시킨 `FA2(n)`를 구현하고, 힌트 2에 따라 `FA(n)`과 `FA2(n)`의 성능을 비교하라.

## 3. 최적화

### 힌트 1: `randn()`, `rand()`

$$
Z \sim N (0,1)
$$

위와 같이 [표준정규분포](https://freshrimpsushi.github.io/posts/normal-distribution/)를 따르는 난수발생시키는 함수는 매트랩에서와 마찬가지로 `randn(n)`으로, 다음 예시처럼 길이가 `n`이고 각 원소가 표준정규분포를 따르는 벡터를 리턴한다.

julia> z = randn(10)
10-element Vector{Float64}:
 -1.310782389377869
 -1.9610344091115333
  2.3925248401432198
  ⋮
 -0.3730980689762752
 -0.6083035817749504
  1.1110122368341526

이와 달리 [유니폼 분포](https://freshrimpsushi.github.io/posts/uniform-distribution/)를 따르게 하려면 `rand()` 함수를 사용하면 된다.

### 힌트 2: 브로드캐스팅

julia> z ^ 2
ERROR: LoadError: MethodError: no method matching ^(::Vector{Float64}, ::Int64)

julia> z .^ 2
10-element Vector{Float64}:
 1.7181504723031553
 3.8456559537194206
 5.7241751107023395
 ⋮
 0.13920216907382538
 0.3700332476002337
 1.2343481903952271

각 원소를 제곱하는 법은 `.^`과 같이 점을 찍어서 제곱하면 된다. 일반적으로 벡터에는 거듭제곱이 정의되어 있지 않기 때문에 이와 같은 벡터 연산이 필요하다.

julia> abs.(z)
10-element Vector{Float64}:
 1.330112275601434
 0.10482038445707342
 0.6899064834783252
 1.237258139091657
 ⋮
 0.293113713408394
 1.2104619980817963
 0.19047088401274126

브로드캐스팅은 대부분의 함수에 적용할 수 있다. 가령 위의 경우에는 절대값을 구하는 함수 `abs()`의 뒤에 점을 찍어 `abs.()`로 각 원소의 절대값을 취한 배열을 얻었다.

### 힌트 3: 행렬연산

$$
\mathbf{y} := \begin{bmatrix} 7 \\ 6 \\ 7 \end{bmatrix} , X = \begin{bmatrix} 6 & 8 \\ 9 & 4 \\ 3 & 10 \end{bmatrix}, W = \begin{bmatrix} w_1 \\ w_2 \end{bmatrix}, \mathbf{b} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}
$$

위와 같은 행렬들에 대해 다음을 만족하는 $W$, $\mathbf{b}$ 를 계산하는 문제가 주어져 있다고 하자.
$$
\mathbf{y} = X W + \mathbf{b}
$$
단, $W$ 의 원소는 $0$ 부터 $1$ 사이의 수다. 이는 임시로 난수 추출을 사용해 다음과 같이 줄리아 코드로 옮길 수 있다. [^4]

[^4]: https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#man-linalg

julia> y = [7; 6; 7]
3-element Vector{Int64}:
 7
 6
 7

julia> X = [6 8 ; 9 4 ; 3 10]
3×2 Matrix{Int64}:
 6   8
 9   4
 3  10

julia> W = rand(2)
2-element Vector{Float64}:
 0.5562849835210015
 0.08542313648610178

julia> b = randn(3)
3-element Vector{Float64}:
  1.0561929458402592
 -1.2382386408346975
  0.41263939042167586

julia> (X * W) + b
3-element Vector{Float64}:
 5.077287938855083
 4.110018756798723
 2.935725705845698

### 3-1 기본과제

힌트 3의 $W, \mathbf{b}$ 를 찾는 것은 **$l_{1}$-손실함수** $\displaystyle L(W,\mathbf{b}) = \left\| \mathbf{y} - \left( X W + \mathbf{b} \right) \right\|_{1}$ 의 함숫값이 $0$ 이 되게끔 하는 것과 같다. 이 함수 `L(W,b)`를 줄리아 코드로 정의하라.

### 3-2 추가과제

`L(W,b)` 가 $1$ 보다 작아질 때까지 `W = rand(2)`과 `b = randn(3)`으로 난수추출을 반복해서 최적해 `W0` 와 `b0` 를 얻고, 최적화가 얼마나 빠르게 진행되는지 기록해서 확인하라. `W`와 `b` 는 더 낮은 값을 얻지 못했을 경우 업데이트 하지 않는다. 예를 들어, 최적화에 성공한 케이스 중 하나는 다음과 같다. `L_`은 손실함수값을 기록한 배열, `W0`, `b0`는 최적해다.

julia> L_
28-element Vector{Float64}:
 Inf
  6.002334586049868
  6.002334586049868
  6.002334586049868
  ⋮
  2.77570601868113
  2.77570601868113
  0.8999024343618416

julia>     W0
2-element Vector{Float64}:
 0.3104322220784894
 0.5791067721039918
 
julia>          b0
3-element Vector{Float64}:
 0.6707623140708989
 0.8189632218454262
 0.9406085326804846
 
julia> X * W0 + b0
3-element Vector{Float64}:
 7.166209823373769
 5.929280308967798
 7.6629729199558705

이 때 최적화에까지 걸린 반복은 27회고, 검산 결과도 `X * W0 + b0`가 `y`와 꽤 비슷한 것을 확인할 수 있다. 최적화 과정을 시각화하면 다음과 같다.


최적화를 기록한 `L_`은 증가하지 않는 함수의 개형을 보이면서, 대상함수값이 감소하지 않은 경우 그 전의 대상함수값을 기록하고 있다.

이 문제는 반드시 함수형으로 구현할 필요는 없다.

## 4. 일급객체

> 컴퓨터 프로그래밍 언어 디자인에서, 일급 객체(영어: first-class object)란 다른 객체들에 일반적으로 적용 가능한 연산을 모두 지원하는 객체를 가리킨다. 보통 함수에 매개변수로 넘기기, 수정하기, 변수에 대입하기와 같은 연산을 지원할 때 일급 객체라고 한다.

### 힌트 1: 수렴성

피보나치 수열에 역수를 취한 $\left\{ F_n^{-1} \right\}$ 는 $n \to \infty$ 일 때 $0$ 으로 수렴하는데, 이 수렴성을 프로그래밍에서는 보통 **특정 임계치**^Threshold^ 아래로 떨어지는지로 판별하곤 한다.

julia> n = 1
1

julia> while true
           if (1/F(n)) < 0.001
               break
           else
               n += 1
           end
       end

julia> n
17

이 예시에서는 오차 $\varepsilon = 10^{-3}$ 를 허용했을 때 $n = 17$ 에서 수렴함을 보였다. 한편 이 경우 어디로 수렴하는지가 정확해서 참값과의 비교가 가능했지만, 그렇지 않은 경우에는 그 반복에서의 항과 현재의 항의 차를 비교하는 식으로 수렴성을 판단한다.

### 힌트 2: 범함수^Functional^

줄리아에서는 함수가 일급객체다. 다시 말해, 함수 자체가 인풋이나 아웃풋이 될 수도 있다. 가령 함수의 덧셈 $h = f + g$ 는 다음과 같이 구현할 수 있다.

julia> h(f,g,x) = f(x) + g(x)
h (generic function with 1 method)

julia> h(sin,cos,π/4)
1.414213562373095

### 4-1 기본과제

$\varepsilon = 10^{-3}$ 이하의 오차를 허용한다. 미분가능한 함수 $f : \mathbb{R} \to \mathbb{R}$ 의 $x \in \mathbb{R}$ 에서의 미분계수를 구하는 함수 $D(f,x)=$`D(f,x)` 를 구현하라.

### 4-2 추가과제

$\varepsilon = 10^{-3}$ 이하의 오차를 허용한다. 적분가능한 함수 $f : \mathbb{R} \to \mathbb{R}$ 의 $[a,b] \subset \mathbb{R}$ 에서의 정적분을 구하는 함수 $I(f,a,b)=$`I(f,a,b)` 를 구현하라.

## 5. 소인수분해

### 힌트 1: 나눗셈

julia> 7 ÷ 2
3

julia> 7 % 2
1

julia> 7 / 2
3.5

줄리아에서 정수의 나눗셈에는 몫 `÷`, 나머지 `%`가 쓰이며, `/`는 실수의 나눗셈을 수행한다. 일반적인 줄리아 코드 편집기에서 `÷`는 텍코드처럼 `\div`를 입력하고 탭(Tab)을 누르면 입력할 수 있다.

### 힌트 2: 배열의 합병과 2차원 배열

julia> [[2,3,5] ; [7,11]]
5-element Vector{Int64}:
  2
  3
  5
  7
 11

julia> [[2,3,5] , [7,11]]
2-element Vector{Vector{Int64}}:
 [2, 3, 5]
 [7, 11]

위 예시는 두 개의 배열을 묶은 배열에 세미콜론 `;`과 쉼표 `,`를 썼을 때 어떤 차이가 있는지를 보여주고 있다.
- 세미콜론 `;`은 두 배열을 이어준다. 그 배열들이 1차원 배열이라면, 그 결과도 1차원 배열이다.
- 쉼표 `,`는 배열의 배열을 만들어준다. 그 배열들이 1차원 배열일 때, 그 결과를 **2차원 배열**이라 한다.

### 힌트 3: 튜플

julia> function pm(a,b)
           return (a+b), (a-b)
       end
pm (generic function with 1 method)

julia> c,d = pm(3,2)
(5, 1)

julia> c
5

julia> d
1

줄리아에서의 튜플은 파이썬과 유사하게 괄호로 묶는 것만으로 사용할 수 있다. 튜플을 대입할 때 여러 변수를 사용하면 순서대로 튜플 내부의 원소를 참조하게 된다.

### 5-1 기본과제

다음과 같이 자연수 `n`의 소인수분해를 배열로 리턴하는 함수 `factorize`를 구현하라.

julia> factorize(12)
3-element Vector{Any}:
 2
 3
 2

### 5-2 심화과제

현재까지도 전세계에서 사용되고 있는 [RSA 공개 키 암호체계](https://freshrimpsushi.github.io/posts/proof-of-rsa-public-key-cryptosystem/)는 [소인수분해 문제의 어려움](https://freshrimpsushi.github.io/posts/factorization/)에 기반하고 있다. 아직 소인수분해는 NP문제지만, 이론적으로는 양자 컴퓨터를 이용해 다항시간 내에 소인수분해를 끝낼 수 있는 **쇼어 알고리즘**이 제안된 바 있다.


효율적이지는 않지만, **에라토스테네스의 체**는 주어진 자연수 이하의 모든 자연수에 대해 소인수분해를 얻는 알고리즘이다. 위 움짤이 묘사하듯 작은 소수부터 그 배수들를 지워나가다보면 결과적으로 모든 소수를 얻게 된다. 다음과 같이 주어진 자연수 $n=$`n` 에 대해 $n$ 이하의 모든 자연수에 대한 소인수분해와 모든 소수를 튜플로 리턴하는 함수 `eratosthenes(n)`를 구현하라.

julia> F, P = eratosthenes(20);

julia> F
20-element Vector{Vector{Int64}}:
 [1]
 [2]
 [3]
 [2, 2]
 [5]
 [2, 3]
 ⋮
 [3, 5]
 [2, 2, 2, 2]
 [17]
 [2, 3, 3]
 [19]
 [2, 2, 5]

julia> P
8-element Vector{Int64}:
  2
  3
  5
  7
 11
 13
 17
 19

#### 모범답안

function sloweratosthenes(n)
    factorized = factorize.(1:n)
    primes = findall(length.(factorized) .== 1)
    push!(factorized[1], 1)
    return factorized, primes
end

### 5-3 도전과제

10만번째까지의 소수를 1초 이내로 계산하는 `eratosthenes`를 구현하라.

julia> @time F, P = eratosthenes(100000);
  0.113450 seconds (100.02 k allocations: 10.489 MiB)

julia> F
100000-element Vector{Vector{Int64}}:
 [1]
 [2]
 [3]
 ⋮
 [3, 3, 41, 271]
 [2, 2, 2, 2, 2, 5, 5, 5, 5, 5]

julia> P
9592-element Vector{Int64}:
     2
     3
     5
     ⋮
 99989
 99991

## 6. 클라인 사원군

### 힌트 1: 구조체

> 
>
> $V = \left\{ e, a, b, c \right\}$ 과 이항연산 $\cdot$ 에 대해, $\left< V , \ \cdot \ \right>$ 을 **클라인 사원군**^{Klein 4-group}이라고 한다.

클라인 사원군은 순환군(Cyclic Group)이 아닌 유한 군 중에서 가장 원소가 적은 군으로, 아벨군(Abelian Group)이면서 원소가 4개인 단 두가지 그룹 중 하나기도 하다.

struct Klein
    explicit::Char
end

e = Klein('e'); 가 = Klein('e')
a = Klein('a'); 나 = Klein('a')
b = Klein('b'); 다 = Klein('b')
c = Klein('c'); 라 = Klein('c')

> C/C++ 프로그래밍 언어에서 구조화 된 데이터를 처리할 때 struct를 사용하는데 이를 구조체라고 한다. 구조화되었다는 말은 의미가 연결되어 한 덩어리로 처리하는 방식을 말한다.

줄리아는 파이썬에서 많은 영향을 받았으나 클래스 대신 스트럭쳐를 택했다. 이 **구조체**는 줄리아가 C로부터 가장 큰 영향을 받은 요소 중 하나로, [강한 타입 언어](https://freshrimpsushi.github.io/posts/type-in-programming/)인 줄리아에 숙련되기 위해서 필수적으로 알아야 하는 개념이다. 위 예시에서 변수들은 캐릭터 `e,a,b,c` 중 하나를 가지며 이들의 차이가 곧 클라인 사원군 내에서의 차이가 된다.

관습적으로 타입의 첫글자는 대문자를 사용하므로, 우리도 `klein`이 아닌 `Klein`을 사용했다.

julia> 가.explicit
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)

변수 `x`에 어떤 원소가 할당되었는지는 R을 제외한 대부분의 프로그래밍 언어가 그러하듯 `x.explicit` 와 같이 `explicit` 필드에 `.`을 찍어서 접근할 수 있다.

islegal(x::Klein) = x.explicit ∈ ['e','a','b','c']

새로운 타입이 생겼으니 새로운 함수를 정의해보자.

julia> islegal(e)
true

julia> islegal(b)
true

julia> islegal(가)
true

julia> d = Klein('d')
Klein('d')

julia> islegal(d)
false

실제 변수의 명명이 어떠하든 클라인 사원군이라면 $(V, \cdot)$ 과 동형(Isomorphic)할 것이다. 위 함수 `islegal`은 `Klein`을 받아 `e,a,b,c` 중 하나인지 아닌지를 체크해주는 함수로, 변수 이름이 `e`든 `가`든 상관 없이 `true`를 반환 했으나 그에 대응되는 `explicit`이 `d`인 경우 거짓을 리턴했다.

### 힌트 2: 오버로딩

파이썬에서는 `+` 연산으로 문자열을 이을 수 있고, `*` 연산으로 문자열을 반복할 수 있다. 반면 줄리아에서는 `*`으로 문자열을 잇고 `^`으로 문자열을 반복한다. 덧셈이 곱셈으로 바뀌었을 뿐 찰떡같이 맞아떨어지고, 사실 [`*`는 수학적으로 나름 이유가 있는 노테이션](https://freshrimpsushi.github.io/posts/how-to-concatenate-strings-in-julia)이다.

julia> "foo" * "bar"
"foobar"

julia> "foo" + "bar"
ERROR: LoadError: MethodError: no method matching +(::String, ::String)

위 결과를 보면 `"foo" + "bar"`는 `MethodError`를 레이즈했다. 이는 이항연산 `+`이 문자열에 대해 정의되어있지 않기 때문이다. 실용성과 별개로, 여전히 파이썬에서와 같이 `+`로 문자열을 잇고 싶다면 문자열에 대해 확장된 `+`을 오버로딩하면 된다.

> **오버로딩(Overloading)**: 같은 이름의 메서드 여러개를 가지면서 매개변수의 유형과 개수가 다르도록 하는 기술[^5]

큰 프로젝트일수록 네임 스페이스(Name Space)를 꼼꼼하게 신경쓰는 편이 좋지만, 실제 구현과 관계없이 메소드의 특정한 이름이 특정한 기능을 암시하는 것은 매우 중요하고 큰 편리함을 가져다줄 수 있다.

[^5]: https://private.tistory.com/25

import Base.+
function +(x::String, y::String)
    return y * x
end

가령 위의 함수는 `+`로 두 문자열을 잇되, 앞뒤를 바꿔주는 식으로 오버로딩했다. 결과는 다음과 같다.

julia> "foo" + "bar"
"barfoo"

### 6-1 기초과제

다음과 같이 변수명에 관계 없이 클라인 사원군의 **항등원**인지 아닌지를 체크하는 함수를 구현하라.

julia> isidentity(e)
true

julia> isidentity(a)
false

julia> isidentity(가)
true

julia> isidentity(다)
false

### 6-2 추가과제

julia> inv(4)
0.25

julia> inv(a)
ERROR: LoadError: MethodError: no method matching inv(::Klein)

줄리아에서 원래 `inv`는 역수를 반환해주는 함수다. 이를 클라인 사원군에 대해 확장하라.

julia> inv(e)
Klein('e')

다시 말해, 클라인 역원군의 원소를 받아서 그 **역원**을 반환하는 함수를 `inv` 이름 그대로 작성하라.

### 6-3 도전과제

연산 `*`에 대해 클라인 사원군을 구현하라. 다음과 같은 연산이 네이티브하게 이루어지길 원한다.

julia> a * b
Klein('c')

julia> c * b
Klein('a')

julia> [e * x for x in [a,b,c]]
3-element Vector{Klein}:
 Klein('a')
 Klein('b')
 Klein('c')

julia> 라 * a
Klein('b')

## 모범답안

### 1. 함수

#### 1-1

function F(n)
    if n ≤ 2
        return 1
    else
        return F(n-1) + F(n-2)
    end
end

#### 1-2

F1(n) = (n ≤ 2 ? 1 : F1(n-1) + F1(n-2))

### 2. 자료구조

#### 2-1

F1(n) = (n ≤ 2 ? 1 : F1(n-1) + F1(n-2))

function FA(n)
    y = []
    for k in 1:n
        push!(y, F1(k))
    end
    return y
end

FA(7)

#### 2-2

function FA2(n)
    result = Int64[]
    for k ∈ 1:n
        if k ≤ 2
            push!(result, 1)
        else
            push!(result, result[k-1] + result[k-2])
        end
    end
    return result
end

FA2(10)

### 3. 최적화

#### 3-1

L(W,b) = sum(abs.(y .- ((X * W) .+ b)))

#### 3-2

W0 = rand(2)
b0 = rand(3)
L_ = [Inf]
while L_[end] ≥ 1
    W0 = rand(2)
    b0 = randn(3)
    L0 = L(W0,b0)
    if L0 < L_[end]
        push!(L_, L0)
    else
        push!(L_, L_[end])
    end
end

X * W0 + b0

using Plots
plot(L_, label = "Loss")

### 4. 일급객체

#### 4-1

f(x) = x^2 + 4x + 4
function D(f,x)
    h = 1
    df = Inf
    while abs(df - ((f(x+h)-f(x)) / h)) > 1e-3
        df = ((f(x+h)-f(x)) / h)
        h /= 2
    end
    return df
end
D(f,3)

#### 4-2

f(x) = x^2 + 4x + 4
function I(f,a,b)
    h = b-a
    ∫fdx = Inf
    while abs(∫fdx - sum(f.(a:h:b) .* h)) > 1e-3
        ∫fdx = sum(f.(a:h:b) .* h)
        h /= 2
    end
    return ∫fdx
end
I(f,0,3)

-->

### 5. 소인수분해

#### 5-1

function factorize(n)
    factors = []
    while n > 1
        for k in 2:n
            if n % k == 0
                n ÷= k
                push!(factors, k)
            end
        end
    end
    return factors
end

#### 5-3

function eratosthenes(n::Integer)
    if n == 1 return [[1]], Nothing end
    if n == 2 return [[1], [2]], [2] end
    primes = [2]
    factorized = [[1], [2]]
    for k ∈ 3:n
        m = k
        for p ∈ primes
            if m % p == 0
                m ÷= p
                temp = [p; factorized[m]]
                push!(factorized, temp)
                break
            end
        end
        if length(factorized) != k
            push!(primes, k)
            push!(factorized, [k])
        end
    end
    return factorized, primes
end
F, P = eratosthenes(20)
F
P

@time F, P = eratosthenes(100000);
F
P

### 6. 클라인 사원군

#### 6-1

isidentity(x::Klein) = x.explicit == 'e'

#### 6-2

inv(x::Klein) = x

#### 6-3

hardtable = 
[e a b c
 a e c b
 b c e a
 c b a e]

import Base.*
function *(x::Klein, y::Klein)
    i = (1:4)[x.explicit .== ['e','a','b','c']]
    j = (1:4)[y.explicit .== ['e','a','b','c']]
    return first(hardtable[i,j])
end

#### 김규엽님의 풀이

import Base.*
function *(x::Klein, y::Klein)
    if islegal(x)
        if isidentity(x)
            return y
        elseif isidentity(y)
            return x
        else
            return setdiff([Klein('a'), Klein('b'), Klein('c')], [x, y])
        end
    else
        @error "inv(x::Kelin) 사용 시, 클라인 사원군에 속하는 원소를 입력해주십시오."
    end
end

#### 권기웅님의 풀이

import Base.*
function *(x::Klein, y::Klein)
    # identity
    if x == Klein('e')
        return y   
    elseif y == Klein('e')
        return x
    # otherwise
    elseif x == Klein('a')
        if y == Klein('a')
            return Klein('e')
        elseif y == Klein('b')
            return Klein('c')
        elseif y == Klein('c')
            return Klein('b')
        end
    elseif x == Klein('b')
        if y == Klein('a')
            return Klein('c')
        elseif y == Klein('b')
            return Klein('e')
        elseif y == Klein('c')
            return Klein('a')
        end
    elseif x == Klein('c')
        if y == Klein('a')
            return Klein('b')
        elseif y == Klein('b')
            return Klein('a')
        elseif y== Klein('c')
            return Klein('e')
        end
    end 
end

import Base.inv
function inv(x::Klein)
    for element ∈ ['e', 'a', 'b', 'c']
        y = Klein(element)
        if x * y == Klein('e')
            return y
        end
    end
end