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

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

ただいまの
回答率

88.62%

int型ぎりぎりの素因数分解がしたい

受付中

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 2,529

chuchutakotako

score 13

 前提・実現したいこと

入力した数値を素因数分解し、計算時間を測るプログラムを作っています。

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

7ケタの数字を入力した場合は無限ループ
52行目のwhile分で無限ループしてしまいます。
それ以上の数字を入力するとsegmentation faultになります。

 該当のソースコード

include<stdio.h>

include<time.h>

define MAX 100

int main(void){
int i;
int j;
int root;
int average[MAX];

unsigned long int start;
unsigned long int end;
unsigned long int elapsed;

scanf("%d",&i);
printf("%d ",i);

start = clock();

average[0]=1;
for(j=1;j<100;j++){
average[j]=(average[j-1]+i/average[j-1])/2;
root=average[j];
}
printf("平方根:%d ",root);
/*平方根を割り出す*/

int a;

int primenumber[MAX];
int number=0;
for(j=2;j<=root;j++){
for(a=2;a<=j;a++){
if(j==a){
primenumber[number]=j;
number++;
}
else if(j%a==0)break;
}
}

/*平方根までの素数を配列に格納*/
int d;
int e[MAX];
int f;
int flag=0;
int check=0;
for(d=0;d<number;d++){
e[d]=0;
check=0;
while(1){
if(i%primenumber[d]==0){
i=i/primenumber[d];
if(i>root){
for(f=2;f<i;f++){
if(i%f==0)break;
else if(f==i-1){
printf("%d*1 ",i);
break;
}
}
}
e[d]++;
}
else break;

}
if(e[d]>0){
printf("%d*%d ",primenumber[d],e[d]);
}

}            

end = clock();
elapsed = end-start;
printf("計算時間:%lu\n",elapsed);
return 0;
}

c言語
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

+4

素数を入れておく配列primenumberは100個しかありませんが、1000000の平方根1000までの素数の数は168個です。つまり、7桁の数字の時に必要になる素数の数に対して、primenumberの配列の大きさがたりず、その範囲を超えたところにアクセスしてしまいます。配列の範囲外アクセスは未定義な動作のため、場合によってはおかしな値にで無限ループしたり、セグメンテーション違反で落ちたります。

対応したい数の最大値に合わせて必要な配列の大きさ(最大の素数の数)を計算し直してください。取りあえずチェックだけするなら、assert()を使うと便利です。

...
if (j == a) {
    assert(number < MAX);
    primenumber[number] = j;
    number++;
} else if (j % a == 0)
...

NDEBUGマクロの有無で有効無効が切り替わるので、チェック用と速度計測の本番用でコードを書き換える必要が無くなります。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2019/04/01 22:18

    できました。。
    返信遅れてすみません。。

    キャンセル

0

タイトルの意味がいまいち理解できていませんが、

前提、実現したいことに

入力した数値を素因数分解し、計算時間を測るプログラムを作っています。 

と書いてあるのでその部分を私なりに実装しました。
質問欄にあるコードを見て思ったのですが、因数分解する部分は関数に切り出すことをおすすめします。

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

#define BUFSIZE 256

void fact(int n);
int check_prime(int n);

int main(void)
{
    char buf[BUFSIZE];
    int n;
    clock_t start,end;

    printf("自然数を入力->");
    fgets(buf,sizeof(buf),stdin);
    n = strtol(buf,NULL,10);
    //printf("%d = ",n);
    start = clock();
    fact(n);
    end = clock();
    printf("処理時間:%d [ms]",end - start);
    return 0;
}

void fact(int n)
{
    int i;

    while(1){
        for(i = 2; i <= sqrt(n); i++){
            if(n % i == 0){
                printf("%d*",i);
                n /= i;
                break;
            }
        }
        if(check_prime(n) == 1){
            printf("%d \n",n);
            break;
        }
    }
}

int check_prime(int n)
{
    int i;
    int flag = 1;

    if(n <= 1){
        flag = 0;
    }
    else if(n <= 3){
        flag = 1;
    }
    else{
        for(i = 2; i <= sqrt(n); i++){
            if(n % i == 0){
                flag = 0;
                break;
            }
        }
    }
    return flag;
}

<実行例>
n = 4857

<結果>
自然数を入力->4857
3*1619 
処理時間:3 [ms]

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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