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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

Q&A

2回答

627閲覧

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

chuchutakotako

総合スコア13

C

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

0グッド

0クリップ

投稿2018/08/03 08:03

前提・実現したいこと

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

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

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言語

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

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

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

C

1... 2if (j == a) { 3 assert(number < MAX); 4 primenumber[number] = j; 5 number++; 6} else if (j % a == 0) 7...

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

投稿2018/08/03 23:03

raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

chuchutakotako

2019/04/01 13:18

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

0

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

前提、実現したいことに

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

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

C

1#include <stdio.h> 2#include <stdlib.h> 3#include <math.h> 4#include <time.h> 5 6#define BUFSIZE 256 7 8void fact(int n); 9int check_prime(int n); 10 11int main(void) 12{ 13 char buf[BUFSIZE]; 14 int n; 15 clock_t start,end; 16 17 printf("自然数を入力->"); 18 fgets(buf,sizeof(buf),stdin); 19 n = strtol(buf,NULL,10); 20 //printf("%d = ",n); 21 start = clock(); 22 fact(n); 23 end = clock(); 24 printf("処理時間:%d [ms]",end - start); 25 return 0; 26} 27 28void fact(int n) 29{ 30 int i; 31 32 while(1){ 33 for(i = 2; i <= sqrt(n); i++){ 34 if(n % i == 0){ 35 printf("%d*",i); 36 n /= i; 37 break; 38 } 39 } 40 if(check_prime(n) == 1){ 41 printf("%d \n",n); 42 break; 43 } 44 } 45} 46 47int check_prime(int n) 48{ 49 int i; 50 int flag = 1; 51 52 if(n <= 1){ 53 flag = 0; 54 } 55 else if(n <= 3){ 56 flag = 1; 57 } 58 else{ 59 for(i = 2; i <= sqrt(n); i++){ 60 if(n % i == 0){ 61 flag = 0; 62 break; 63 } 64 } 65 } 66 return flag; 67}

<実行例>
n = 4857

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

投稿2018/08/03 09:13

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問