高校数学の質問スレ Part410

[0320 １３２人目の素数さん 2021/02/28(日) 12:25:09.25 ID:acOwFvcK]

>>317
まず素数のリストp_1(=2),p_2(=3),p_3(=5),...を作っておいて、
関数f(N,p_n)を
f(N,p_1)=[N/p_1]=[N/2]
f(N,p_n)=[N/p_n]- Σ(k=1,n-1)f([N/p_n],p_k)
と定義して、f(1000,2),f(1000,3),...を計算するってこと。
計算量が減るんじゃない？