誤って現れたエラトネスの体(15877号)

白駿-誤りを体現するエラトステネスの体(15877号)
エラト・テネスのふるいは素数を求める方法です.
言葉で説明を聞くより、上のリンクの画像を見れば理解できます.
簡単に言えば、nの小数を求める場合、1<=x<=sqrt(n)sqrt(n)sqrt(n)sqrt(n)sqrt(n)からxまでのすべての倍数を除き、残りの数字は小数となる.
実際、この問題はエラトスのふるいとは関係ない.説明しただけです.

逆にこの問題はちょうわすうれつ題であり,上記のコード意識の中で協調数列の規則が発見されたためである.
nを12とする
i=1->1、2、3、4、5、6、7、8、9、10、11、12(12個)
i=2->1,3,5,7,9,11(6個)
i=3->1,4,7,10(4個)
i=4->1,5,9(3個)
i=5->1,6,11(3個)
i=6->1,7(2個)
i=7->1,8(2個)
i=8->1,9(2個)
i=9-10(2個)
i=10->1.11(2個)
i=11->1,2(2個)
i=12->1(1個)
iが1,nの場合、その値は常に固定されるので、結果値にn+1を加算し、他の演算を省略することができる.
しかし、与えられたnが1である場合、n+1ではなく、1であるべきである.
協調数列の核心は同じ値を持つ区間を求め,iごとにどのような値があるかを考えることである.
各iの値は1+(n−1)/iであることがわかる.(うなずく、発見される、証明できない)
調和数列も実はこれを用いて軽く得られるが、調和数列は通常n/(n/i)n/(n/i)n/(n/i)の数列であるため、nの代わりにn−1を用いるのが適切である(分母の素数点が捨てられる).
たとえば、
n=12,i=4を加えて試験したところ,1+(11)/4=4,(11)/(11/4)=5であった.
つまり、4~5は3の値を持つ.
i=5は省略できるので、i=6を求めると
1+(11)/6=2,(11)/(11/6)=11.
すなわち、6〜11は1の値を有する.

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

unsigned long long n;

int main(void)
{
	cin >> n;
	unsigned long long ans = n;
	for (unsigned long long i = 2, j = 0; i < n; i = j + 1) {
		j = (n - 1) / ((n - 1) / i);
		unsigned long long num = 1 + (n - 1) / i;
		ans += (j - i + 1) * num;
	}
	if(n != 1)
		ans++;
	cout << ans << "\n";
	return 0;
}