こんにちは
まず初めに
他の方もおっしゃるとおり
倍精度浮動小数点数 任意精度演算
で実装するのがいいと思います。
質問欄にあるソースコードを見て、質問者もその方針で進めていると思います。
しかし、他の方法を思いついたのでその方法を説明したいと思います。
あまり参考にならないかもしれませんが、
一応、求めたいものは求まったので少しでも参考になれば幸いです。
どんな方法で実装するのか?
そもそもint
やlong
ではなくdouble
で求めたかを考えるとそれは
結果がとても大きな自然数であり、int
やlong
ではオーバーフローしてしまうからです。
そこで考えたのは各桁をそれぞれ配列に格納すればいいと思いました。
各桁の数字は0以上9以下なのでint
で十分に収まります。
(i)初期化として、配列の0番目を1それ以外は0とする。
(ii)配列に格納されている数字をそれぞれ2倍する。
(iii)配列に格納されている数字が10を超えた場合、次の桁へ繰り上げる。
(iv) (ii),(iii)をそれぞれn回繰り返す。
(v) 一桁目(配列の0番目)を1引く.
以下、私が書いたソースコードを載せておきます。
注意
(i)今回は100番目のメルセンヌ数を求めたいので、配列の要素数は31くらいでいいですが、
もっと大きなメルセンヌ数を求めたい場合を考え,配列の要素数を100にしています。
(ii) n桁目の数字は配列のn - 1番目に格納されていますが、表示するときは、逆順にする必要があります。
例えば、1桁目の数字は配列の0番目に格納されていますが、1桁目は数字の一番右にあります。
しかし、for
文で回すときカウントする数字を0から回すと1桁目が1一番左に表示されます。
そのため、、for
文で回すときカウントする数字を(桁数 - 1)から回す必要があります。
C
1#include <stdio.h>
2#include <stdlib.h>
3
4#define BUFSIZE 256
5#define MAX_NUMBER 100
6
7void Mersenne_primes(int);
8
9int main(void) {
10
11 char buf[BUFSIZE];
12 int n;
13
14 fgets(buf,sizeof(buf),stdin);
15 n = atoi(buf);
16 Mersenne_primes(n);
17
18 return 0;
19}
20
21void Mersenne_primes(int n)
22{
23 int answer[MAX_NUMBER];
24 int carry = 0; //桁上がり
25 int digit = 1; //現在の桁数
26 int i,j;
27 int num;
28 for(i = 0; i < MAX_NUMBER; i++){
29 answer[i] = 0;
30 }
31 answer[0] = 1;
32
33 for(i = 0; i < n; i++){
34 for(j = 0; j <= digit; j++){
35 num = answer[j] * 2 + carry;
36 carry = num / 10;
37 answer[j] = num % 10;
38 if(carry > 0 && j + 1 > digit){
39 digit++;
40 }
41 }
42 carry = 0;
43 }
44 answer[0]--;
45
46 for(i = digit; i >= 0; i--){
47 printf("%d",answer[i]);
48 }
49}
<結果>
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/05/22 05:44
2018/05/22 05:49
2018/05/22 10:25