<에라토스테네스-신촌우왕 체식>은 다음 글을 참조하면 됨.
https://gall.dcinside.com/board/view/?id=mathematics&no=421526
gall.dcinside.com
에라토스테네스-신촌우왕 체식 E(n)은 수열로 표현하면 다음과 같다.
E(n) = 0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, ...
비소수번째 항은 0이고 소수번째 항은 그 소수인 수열이다.
한편 양변을 n으로 나누면
E(n)/n = 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, ...
비소수번째 항은 0이고 소수번째 항은 1인 수열이다.
E(n)에서 1번째로 0이 아닌 항은 2로 P(1) 이다.
E(n)에서 2번째로 0이 아닌 항은 3으로 P(2) 이다.
E(n)에서 3번째로 0이 아닌 항은 5로 P(3) 이다.
...
일반적으로 E(n)에서 k번째로 0이 아닌 항은 P(k)이다.
이제 타우 함수를 다음과 같이 정의하자.
tau(x, y)=0 (x=y)
tau(x, y)=1 (x!=y)
한편 pi(N)은 N 이하의 소수 개수이므로 다음이 성립함을 알 수 있다.
E(n)이 소수이면 0과 다르므로 tau(E(n), 0) = 1이 되고,
소수가 발견될 때마다 1을 더하므로
결국 그것을 모두 합하면 1부터 N까지 소수의 개수가 되는 것이다.
E(n) 대신 E(n)/n을 써도 같은 결과를 얻을 수 있으나 더 간단한 형태인 E(n)을 선택하자.
한편 소수수열의 일반항은 다음과 같이 알려져 있다.
p(k)=min{n∈N∣π(n)=k}
어떻게 계산하는 지 알아보자.
p(4)를 생각해보자.
k=4인 경우이므로
p(4)=min{n∈N∣π(n)=4} = min{7, 8, 9, 10}=7
1부터 n까지 소수의 개수가 4개이려면 n=7, 8, 9, 10임을 알 수 있고 그때 n의 최소값은 7이다.
즉 P(4) = 7이다.
한편이므로
E(n)을 사용하여 P(k)를 표현하면 다음과 같은 식을 얻게 된다.
신우님 그간 잘 지내셧나요
옙
뭔가 흥미로워 보이는데 지금 선형대수 공부해야돼서 나중에 이해할 거임.