裏 RjpWiki

文字通り,RjpWiki の裏を行きます
R プログラム コンピュータ・サイエンス 統計学

2 〜 n までの整数の約数の個数

2020年09月03日 | ブログラミング

2 ~ n までの整数を素因数分解したとき,約数(素数) p が何個あるか数える。

p = 7 のとき 35 = 5 * 7 なので 1 個,49 = 7 * 7 なので 2 個である。

素朴にプログラムしてみると,以下のようになる(素朴すぎるということがすぐわかる)。

> count_factors0 = function(n, p) {
+   count = 0
+   for (i in 2:n) {
+     while (i %% p == 0) {
+       count = count + 1
+       i = i %/% p
+     }
+   }
+   return(count)
+ }

2 〜 50 の約数 7 の個数は,

> count_factors0(50, 7)
[1] 8

ただし,大きな n に対して求めようとすると,とんでもない時間が掛かる。

> system.time({
+   print(count_factors0(50000000, 7))
+ })
[1] 8333328
   ユーザ   システム       経過  
    14.356      0.030     14.386 

for ループと while ループの使い方が悪いのだ。以下のようにすれば瞬殺である。

> count_factors2 = function(n, p) {
+   count = 0
+   while (n > 0) {
+     count = count + n %/% p
+     n = n %/% p
+   }
+   return(count)
+ }

> system.time({
+   print(count_factors2(50000000, 7))
+ })
[1] 8333328
   ユーザ   システム       経過  
     0.004      0.000      0.004 

ちょっとわかりにくいが,以下のように再帰関数で定義するとわかりやすいかな。

> count_factors1 = function(n, p) {
+   if (n == 0) {
+     return(0)
+   } else {
+     return(n %/% p + Recall(n %/% p, p))
+   }
+ }

> system.time({
+   print(count_factors1(50000000, 7))
+ })
[1] 8333328
   ユーザ   システム       経過  
     0.005      0.000      0.005 

コメント (2)   この記事についてブログを書く
«  外積の和 | トップ | 学術会議任命拒否問題 »
最新の画像もっと見る

2 コメント

コメント日が  古い順  |   新しい順
Unknown (nakazawa)
2020-09-03 17:26:57
function(n, p) { i=1; c=0; while(n > p^i) { c = c + (n %/% p^i); i = i+1 }; return(c) }
で良くないですか?
Unknown (r-de-r)
2020-09-05 19:21:16
なるほど!

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。

ブログラミング」カテゴリの最新記事