質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.86%

  • C

    3319questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

標準入力から与えらる正整数 m を読み取り、m 番目のメルセンヌ数を書き出すプログラムを組みたいです

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 194

Hisa-pon777

score 3

 前提・実現したいこと

標準入力から与えらる正整数 m を読み取り、m 番目のメルセンヌ数を書き出すプログラムを組みたいです。 
※メルセンヌ数とは、 2^m-1 です。

 発生している問題・エラーメッセージ

標準入力に100を入れ実行すると、1267650600228229401496703205376 になります。
正解は1267650600228229401496703205375 なのですが・・・
54以降はなぜか、1足されたものが出力されます。

 該当のソースコード

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[]) {
    double m;
    double a;
    double b;

    scanf("%lf", &m);

    a = pow(2,m);
    b = (a-1);

    printf("%.0f", b);
    printf("\n");
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+5

doubleは浮動小数点数型です。

浮動小数点数というのはざっくり言うと
(+/-)1.aaaa x 2^bbbb
というような数値表現です。例えば1.01001 x 2^5のように。

そして、doubleの場合、aaaaの部分(仮数部)は52ビット、2進数で52桁と決まっています。
1.の部分も合わせると、53桁になります。

(2^53)-1 は2進数で1111111..11(1が合計53個)ですから、
doubleで誤差なく表すことができるメルセンヌ数はm=53までとなります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/22 14:44

    m=53以上の値を求めるにはどのようにすればよいのでしょうか?

    キャンセル

  • 2018/05/22 14:49

    そういうのを「多倍長整数」といいます。
    多倍長整数を扱うライブラリを探してください。
    無ければ自分で作りましょう。

    キャンセル

  • 2018/05/22 19:25

    皆さん分かりやすい回答ありがとうございます。
    解決できました。

    キャンセル

checkベストアンサー

+3

こんにちは

 まず初めに

他の方もおっしゃるとおり

倍精度浮動小数点数 任意精度演算

で実装するのがいいと思います。
質問欄にあるソースコードを見て、質問者もその方針で進めていると思います。

しかし、他の方法を思いついたのでその方法を説明したいと思います。
あまり参考にならないかもしれませんが、
一応、求めたいものは求まったので少しでも参考になれば幸いです。

 どんな方法で実装するのか?

そもそもintlongではなくdoubleで求めたかを考えるとそれは
結果がとても大きな自然数であり、intlongではオーバーフローしてしまうからです。
そこで考えたのは各桁をそれぞれ配列に格納すればいいと思いました。
各桁の数字は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)から回す必要があります。

#include <stdio.h>
#include <stdlib.h>

#define BUFSIZE 256
#define MAX_NUMBER 100

void Mersenne_primes(int);

int main(void) {

    char buf[BUFSIZE];
    int n;

    fgets(buf,sizeof(buf),stdin);
    n = atoi(buf);
    Mersenne_primes(n);

    return 0;
}

void Mersenne_primes(int n)
{
    int answer[MAX_NUMBER];
    int carry = 0; //桁上がり
    int digit = 1; //現在の桁数
    int i,j;
    int num;
    for(i = 0; i < MAX_NUMBER; i++){
        answer[i] = 0;
    }
    answer[0] = 1;

    for(i = 0; i < n; i++){
        for(j = 0; j <= digit; j++){
            num = answer[j] * 2 + carry;
            carry = num / 10;
            answer[j] = num % 10;
            if(carry > 0 && j + 1 > digit){
                digit++;
            }
        }
        carry = 0;
    }
    answer[0]--;

    for(i = digit; i >= 0; i--){
        printf("%d",answer[i]);
    }
}


<結果>
イメージ説明

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/22 19:23

    詳しい回答ありがとうございました。
    おかげさまで理解できました!

    キャンセル

  • 2018/05/22 20:53

    質問内容とは全く別の方針だったのですが、役に立ったので良かったです。
    ちなみに私は最初,質問のタイトルを見てメルセンヌ素数と勘違いをしました。(笑)

    キャンセル

  • 2018/05/22 20:55 編集

    ちなみに計算したところ,配列の要素数が100(つまり100桁)で求めることができるの自然数の最大値は2^332 - 1です。

    キャンセル

  • 2018/05/24 07:20

    勘違いさせてすみません( ;∀;)
    有難うございました。( ´∀` )

    キャンセル

  • 2018/05/24 12:06 編集

    いえいえ、これは、私の勘違いなので....(おそらく数学のメルセンヌ素数と完全数が好きなのが原因)

    キャンセル

+2

double ではなくて long などで試せばおかしな値になってしまうのでわかりやすいのですが、コレは double 計算精度を超える値を使っていることによる丸め誤差ですね。
たとえば、 a が巨大な数になった時、大きな値を表現するためのビットに対して -1 などの小さな値は決められた数のビット数では表現できません。

a = 10000000000000000;
b = a - 1;

もし具体的にこれらの値を計算したい場合は、「任意精度演算」などを参照すると良いと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/22 19:24

    初めて知りました。とても参考になりました。ありがとうございます。

    キャンセル

+1

倍精度浮動小数点数

これをみて、2の100乗という数値がどういう表現になるか考えてみましょう。
そして、そこから1を引く、ということがどういうことかを考えると、おのずと理解できるかと。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/22 19:26

    なるほどです。よく理解できました。有難うございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.86%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    身長と標準体重の対応表のつくりかた

    こんな模範解答が本にありましたが、他の方法を知っている方がいましたら教えてください。答えに不満というわけではないのですが、 ほかの方法もできれば知りたいです。 宜しくお願いします。

  • 解決済

    結果の表示について

    課題で、 キーボードから入力された数値の平均を計算して表示し、平均以上の数値、平均より小さい数値を表示するプログラムを考えているのですが、 実行例 ./a.out

  • 受付中

    【C言語】冗長だと思う数字入力プログラムを改善したい

    以下のプログラムは3つの数字をスペース区切りで入力して、入力した数字を改行区切りで出力するというコードです。 C言語はあまり慣れていないので、以下のコードに冗長さを感じますが何か改

  • 解決済

    C言語:整数の小数点以下切り上げ方法

    ceilは使わずに整数型aの+20%した値を小数点以下切上げで求めるにはどうしたらよいでしょうか?

  • 受付中

    プログラムを見やすく改良したい

    正常に動くプルグラムを見やすく改良したい。 具体的に教えていただければありがたいです。セグメンテーションフォルトでベスト7まで表示して停止します。173行あたりだと思うのですが、よ

  • 解決済

    別のソースファイルの関数を別のソースファイルで使えるようにしたい

    別のソースコードに記載されている関数の値を別のソースファイルの関数に使いたいのですが、どうやって書けばいいですか? a.cの中 double GO_MONTE_CARLO::G

  • 解決済

    C言語でrand関数を使った?%の確率で任意の処理を行う方法

    rand関数で1から100までの乱数を生成して、もし30なら30%の確率で任意の処理をさせるコードを教えてください。 include <stdio.h> include <st

  • 受付中

    call/cc, lambdaについて

    授業でLisp, Schemeについて軽く触れる必要があった者です。 普段はPython, Cくらいしか使いません。紹介程度に扱われたのであまり深く首を突っ込みたくありません(わが

同じタグがついた質問を見る

  • C

    3319questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • トップ
  • Cに関する質問
  • 標準入力から与えらる正整数 m を読み取り、m 番目のメルセンヌ数を書き出すプログラムを組みたいです