プログラミングのお題スレ Part18
(ID:
mk/D54YH
のみ表示中)
戻る
589
デフォルトの名無しさん
[sage]
AAS
NG
>>588
√n以上の最小の約数をdとして上むき探索に必要な時間はすうがく/d-√n\、下向き探索のそれは\√n-n/d/ (/〜\と\〜/はfloorとceiling)
差は/d-√n\-\√n-n/d/ =\d+n/d-2√n/はam≧gmと\〜/の広義単調性から0以上で上むき探索は素数であるか否かに限らず常に計算量は同じかそれ以上
素数であるか予備検査しても結局上向きに探索したら計算量は同じ以上かかる
2020/09/20(日)10:19:03.22(
mk/D54YH.net
)
戻る
ver.151005sp