質問

 nが与えられたとき、その正の約数をすべて求めるプログラムを書け。 
 これは擬似言語でも、Basicでもいいそうです。
 初心者なのでわかりません。宜しくお願いします。

通報する

回答 (4件)

以下に処理の流れとプログラムを記します。プログラムと照らし合わせて読んでください。

約数とは、「因数を掛け合わせたもの」ですよね?
だからまず因数を求める関数を作成しました。(関数:subFactorization)
そのとき注意すべきは
10の因数を求めるのには5まで、7の因数を求めるには4までに因数がないときはそれ以上の値に因数は存在しないという点です。なので途中でそのリミットになったら抜ける条件を追加しました。(変数:lngRimitがそれにあたります。)



次にその因数を掛け合わすために、その因数を順順に取り出す関数を作成しました。(関数:subMultiplyMatrix)
実際に例をあげると最初に210を因数分解した場合
3,5,7という値が得られます。これらを掛け合わせるとき



3×5
3×7
5×7
3×5×7
という7パターンがあります。
この7パターンの値を配列に収めるようなループが必要でした。(プログラム中のi,jを使用してループしてるのがその部分です)
次にその配列内の値を乗算する関数を作成しました。(関数:subMultiplyMatrix)
しかし、これだけではだめでした。
210だから因数は[3,5,7]だけど、12のときは[2,2,3]という値を得ます。この条件でできるパターンは



2×2
2×3
2×2
2×2×3
となり、重複する値が返ってきます。これではこまります。
なので答えを収める変数をコレクションで宣言し、値のセットをするときに"KEY"という文字列と値を組み合わせたKEYを同時にセットし、重複した値を記憶しないようにしました。(KEY
& wkLng となってる部分です。)
ちなみにOn Error Resume Next
というのが書いてありますが、これがないと、「重複したキーが存在する」というエラーが生じます。

あとは単なるメッセージボックスに出力をしてるだけです。環境を特に書いてなかったので、Join関数を使用してます。VB6限定ですが、大丈夫かな?



以上が処理の流れです。


いやーホント勉強になりました。



以下のソースを貼り付けて見てください。
Option Explicit
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" ( _
  Destination As Any, _
  Source As Any, _
  ByVal Length As Long _
)


Private lngAry()  As Long '因数記憶用の配列
Private lngCnt   As Long '因数のカウンタ

Sub Main()
  Dim lngDef     As Long '初期値
  Dim ansCollection  As Collection  '答えの入るコレクション
  
  Dim i    As Long
  
  '初期値を得る
  On Error GoTo PGMERR
  lngDef = InputBox("", "初期値を入力してください")
  On Error GoTo 0
  
  '初期値が1未満をエラーとします
  If lngDef < 1 Then GoTo PGMERR
  
  '因数カウンタの初期化
  lngCnt = 0
  '因数記憶用の配列を初期化
  Erase lngAry
  
  
  '因数分解をする
  Call subFactorization(lngDef)
  
  
  'コレクションを初期化
  Set ansCollection = New Collection
  'とりあえず1を追加
  ansCollection.Add 1, "KEY1"
  '配列の中身を順に掛け合わせ、コレクションに追加する
  Call subMultiplyMatrix(lngAry, ansCollection)
  
  
  '答えの出力
  Call ansOut(ansCollection)
  
PGMEND:
  Exit Sub
PGMERR:
  Call MsgBox("初期値に不正な値が入力されました")
End Sub


'因数分解
Sub subFactorization(inLng As Long)
  Dim i      As Long
  Dim lngRimit  As Long
  
  '中間の値を求める(切り上げ)
  lngRimit = Int((inLng / 2 * 10 + 9) / 10)
  
  For i = 2 To inLng
    '割ってあまり0のとき、因数とする
    If (inLng Mod i) = 0 Then
      '因数を記憶
      ReDim Preserve lngAry(lngCnt) As Long
      lngAry(lngCnt) = i
      '因数のカウンタを増やす
      lngCnt = lngCnt + 1
      '因数で割った値でさらに因数分解
      Call subFactorization((inLng / i))
      Exit For
    End If
    
    '中間の値になっても因数が見つからないとき、引数自身が因数とする
    If i >= lngRimit Then
      '因数を記憶
      ReDim Preserve lngAry(lngCnt) As Long
      lngAry(lngCnt) = inLng
      '因数のカウンタを増やす
      lngCnt = lngCnt + 1
      Exit For
    End If
  Next i
End Sub


'掛け算マトリックス
Sub subMultiplyMatrix(inlngAry() As Long, inColection As Collection)
  Dim wklngAry() As Long
  
  Dim i    As Long
  Dim j    As Long
  Dim wkLng  As Long
  
  '因数に同じ値が存在するときに発生するエラーを無視させる
  On Error Resume Next
  For i = 0 To lngCnt - 1
    For j = 0 To (lngCnt - 1) - i
      Call copyAry(wklngAry, inlngAry(j), i + 1)
      wkLng = subMultiply(wklngAry)
      inColection.Add wkLng, "KEY" & wkLng
    Next j
  Next i
  On Error GoTo 0

End Sub


'配列の中身を掛け算して値を返す関数
Function subMultiply(inlngAry() As Long)
  Dim i    As Long
  
  subMultiply = inlngAry(0)

  For i = LBound(inlngAry) + 1 To UBound(inlngAry)
    subMultiply = subMultiply * inlngAry(i)
  Next i

End Function


'配列の中身をエリアの分だけコピーする関数
Sub copyAry(inDest() As Long, inSrc As Long, inArea As Long)
  ReDim inDest(inArea - 1) As Long
  Call CopyMemory(inDest(0), ByVal VarPtr(inSrc), ByVal LenB(inSrc) *
inArea)
End Sub


'答えの出力
Sub ansOut(inCollection As Collection)
  Dim wkStr    As String
  Dim ansCount  As Long
  Dim wkStrAry() As String
  Dim i      As Long
  
  ansCount = inCollection.Count
  
  ReDim wkStrAry(ansCount - 1) As String
  
  For i = 1 To ansCount
    wkStrAry(i - 1) = inCollection.Item(i)
  Next i
  
  wkStr = "答えは[" & Join(wkStrAry, ",") & "]です"
  MsgBox wkStr
End Sub

回答がでてるんで、よろしいかと思いますが、
ループは与えられた数のルートをとったものまでで
よいはずです。
そのためには、あまりが0となったときの商も
約数とすればよいかと思います。

この回答へのお礼

ありがとうございました。参考にいたします。

最近ツッコミ専門になりかけている...。
yusuke5111さんのやり方が最も簡単ですね。
ただし、n自体もnの約数なので
for( i=1; i<=n; i++ ){
とすべきですね。

この回答へのお礼

勉強になります。ありがとうございます。

C言語で、単純に

void main( int ac, char* av[] )
{
int i,m,n;
if( ac != 2 ) return;
m = atoi( av[1] ); /* 数字を取得 */
if( m < 0 ) n = -1 * m; /* 負の場合 */
else n = m; /* 正の場合 */
for( i=1; i<n; i++ ){
if( n % i == 0 ){ /* 余りが0の場合iはnの約数 */
printf("%d\n", i);
}
}
}

これで、正の約数はすべて得られるが、nが十分大きい場合結果が出るまでに時間がかかり、負荷が高いのでちょっと問題です。
多分、間違いなくもっと良い回答例があるとは思いますが、一例ということでこれでどうでしょうか。

この回答へのお礼

ありがとうございました。助かります。

このQ&Aは役に立ちましたか?1 件

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

新しく質問する

注目の記事

おしトピにAndroid版アプリが登場

話題のトピックにさくっとコメントできる「おしトピ」に Android版アプリが登場! もっと身近に使いやすくなりました。
今ならダウンロードで話題の掃除ロボットや全天球カメラが 当たるプレゼントキャンペーンも実施中。


新しく質問する

このカテゴリの人気Q&Aランキング

毎日見よう!教えて!gooトゥディ