すべての約数を求める
整数の約数とはある整数Xを割り切ることのできる整数のことです。これを求めるためには、1から順番に実際に割ってみて割り切ることができる数を集めればよいということになります。
|
1 2 3 4 5 6 7 8 9 10 11 |
List<long> GetDivisor(long value) { for(i = 1; i <= value; i++) { if(value % i == 0) { rets.Add(i); } } return rets; } |
ただ、あまり効率のよい方法とはいえません。
まず約数を調べたい数の半分よりあとは調べるのは時間の無駄です。絶対に割り切ることはできません。また1以外の最小の約数で約数を調べたい数を割れば、その数以外の最大の約数を得ることができます。
1以外の最小の約数を得ることができれば割る数の最大値を特定することができるのです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
List<long> GetDivisor(long value) { // 0や負数はnullを返す if(value < 1) return null; List<long> rets = new List<long>(); // 1は必ず約数となる rets.Add(1); // 1と2は個別に考える if(value == 1) return rets; if(value == 2) { rets.Add(2); return rets; } // 3以降の場合 long ceilingSqrt = (long)Math.Ceiling(Math.Sqrt(value)); // 1以外に割り切れる自然数を探す // ceilingSqrtまで探しても1以外に割り切れる自然数がみつからない場合は素数 int i = 2; for(i = 2; i <= ceilingSqrt; i++) { if(value % i == 0) { rets.Add(i); break; } } // 素数だった場合は引数をリストに格納してそれを返す if(rets.Count == 1) { rets.Add(value); return rets; } // i は1以外の最初の約数 // その数以外の約数の最大値は value / i である。 long max = value / i; for(i++; i <= max; i++) { if(value % i == 0) rets.Add(i); } // その数は必ず約数である。 rets.Add(value); return rets; } |
これは1から10,000までの約数を出力するメソッドです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
private void button1_Click(object sender, EventArgs e) { string ret = ""; for(int i = 1; i < 10000; i++) { var divisors = GetDivisor(i); string[] ar = divisors.Select(x => x.ToString()).ToArray(); string str = String.Join(", ", ar); ret += String.Format("{0}の約数\n{1}\n{2}\n", i, str, kanzen); } richTextBox1.Text = ret; } |
完全数を求める
ところで自分自身を除いた約数すべての和が自分と等しい数を完全数と言います。6の6以外の約数は1と2と3です。全部足すと6になります。
これは完全数を求めるメソッドです。引数の min と max は調べたい範囲の最小値と最大値です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
List<int> GetPerfectNumber(int min, int max) { List<int> ret = new List<int>(); for(int i = min; i < max; i++) { var divisors = GetDivisor(i); if(divisors.Sum() == i * 2) { ret.Add(i); } } return ret; } |
実際に10,000くらいの値を入力すると
6
28
496
8128
と出力されます。
|
1 2 3 4 5 6 |
private void button1_Click(object sender, EventArgs e) { List<int> ret = GetPerfectNumber(1, 1 * 10000); string[] ar = ret.Select(x => x.ToString()).ToArray(); richTextBox1.Text = String.Join("\n", ar); } |
次の完全数はどうなっているのでしょうか？ GetPerfectNumberメソッドの引数を大きな値にすると時間がかかります。
メルセンヌ素数から完全数を求める
2のp乗から1を引いた形をした自然数をメルセンヌ数といいます。メルセンヌ数のなかには素数があり、メルセンヌ素数といいます。
メルセンヌ素数（2^p-1）に2のp-1乗（2^(p-1)）を乗じると完全数になるという法則があります。これを使えばメルセンヌ素数から完全数を発見することができます。
下のコードを実行してみると2の31乗はメルセンヌ素数であることがわかります。次のメルセンヌ素数はlong型には収まらないようです（p=61にするとさんざん待たされた上に負数が表示される）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
private void button2_Click(object sender, EventArgs e) { int p = 31; List<long> ret = new List<long>(); for(int i = 1; i <= p; i++) { long mersenne = (long)Math.Pow(2, i) - 1; if(IsPrime(mersenne)) { long value = mersenne * (long)Math.Pow(2, i - 1); ret.Add(value); } } string[] ar = ret.Select(x => x.ToString("#,0")).ToArray(); richTextBox1.Text = String.Join("\n", ar); } |
IsPrimeメソッドは
を参照してください。
出力結果
6
28
496
8,128
33,550,336
8,589,869,056
137,438,691,328
2,305,843,008,139,952,128
