fork download
copy 
  1. No106 O(n)解法
  2.  
  3. min_p[n] = nの一番小さい素因数
  4. cnt[n] = nの素因数の種類
  5. とします
  6.  
  7. * min_pの計算
  8. いま考えている数をnとして p <= min_p[n] となるような 素数p を持ってくると min_p[n * p] = p になります
  9. これを使い min_p テーブルを更新していくと O(n) で表を埋めることができます
  10. 参考)https://code.google.com/p/teamscl/source/browse/trunk/3.+Sieve+of+Eratosthenes+in+linear+time.txt?spec=svn12&r=12
  11.  
  12. * cntの計算
  13. nが素数である場合 cnt[n] = 1
  14. nが合成数である場合
  15. - min_p[n / min_p[n]] == min_p[n] であれば cnt[n] = cnt[n / min_p[n]]
  16. - そうでないなら cnt[n] = cnt[n / min_p[n]] + 1
  17.  
  18. * 実装例
  19. http://y...content-available-to-author-only...r.me/submissions/6704
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wIDdU8
language:
Text (text 6.10)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!