プログラマ専用SNS ミクプラ

[1] 質問文
　[1.1] https://projecteuler.net/problem=23をC言語を使って解きたいです。
　[1.2] 2つの過剰数の和で書き表せない正の整数の総和を求めるのに、
・要素数28123+1，1で初期化した配列を用意する
・[過剰数の和]番目の要素を1から0にする
・番目（？）と要素を掛け算して総和を出す（過剰数の和で書き表せるものの要素は0なので掛け算して0にできるから）
という方法を取ろうと思っています。

コード:

#include <stdio.h>

int isAbundantNumber(int x){
    int sum = 0;
    for(int i = 1; i < x; i++){
        if(x % i == 0){
            // printf("%d\n", i);
            sum += i;
        }
    }
    // printf("%d\n", sum);
    if(sum > x){
        // printf("YES\n");
        return 1;
    }
    return 0;
} 

int main(){
    int abd[7000];  /*過剰数リスト*/
    int nums[28123 + 1];
    int cnt = 1;
    int ans = 0;
    int i, j, a, b;

    // 配列初期化
    for(i = 0; i < 7000; i++){
        abd[i] = 0;
    }
    for(i = 0; i < 28123 + 1; i++){
        nums[i] = 1;
    }

    // 過剰数リストをつくる
    for(i = 1; i <= 28123; i++){
        if(isAbundantNumber(i)){
            // printf("abd[%d] = %d\n", cnt, i);
            abd[cnt] = i;
            cnt++;
        }
    }
    // 2つの過剰数の和で書き表せない正の整数の総和を求めよ.
    for(i = 1; i < cnt; i++){
        printf("%d\n", i);
        for(j = i; j < cnt; j++){
            nums[abd[i] + abd[j]] = 0;
        }
    }

    for(i = 0; i < 28123 + 1; i++){
        printf("%d\n", i);
        ans += i * abd[i];
    }

    printf("ans = %d\n", ans);


    return 0;
}

　[1.3] 問題はこの部分です。実行時にここのprintf文が1775までしか表示されません。想定では6965まで出力されるはずでした。エラー文はありません。

コード:

    // 2つの過剰数の和で書き表せない正の整数の総和を求めよ.
    for(i = 1; i < cnt; i++){
        printf("%d\n", i);
        for(j = i; j < cnt; j++){
            nums[abd[i] + abd[j]] = 0;
        }
    }

　[1.4] 途中で止まってしまう理由と解決方法が知りたいです。

[2] 環境　
　[2.1] OS ： Windows 10
　[2.2] コンパイラ名： gcc

[3] その他
　・（Cは大学で一通りやったのになんにもおぼえてなくてつらい）

yk230 さんが書きました: ↑
4年前
コード:
    for(i = 0; i < 28123 + 1; i++){
        printf("%d\n", i);
        ans += i * abd[i];
    }

ここで配列の範囲外にアクセスしているので、未定義動作です。
したがって、任意の挙動が許されます。

返信ありがとうございます。ここは変数を間違えていて、正しくはこうでした。

コード:

    for(i = 1; i < 28123 + 1; i++){
        printf("%d, %d\n", i, nums[i]);
        ans += i * nums[i];
    }

ここを直しても止まっちゃう問題は解決しませんでした。

コード:

int main(){
    int abd[7000];  /*過剰数リスト*/
    int nums[28123 + 1];

　通常、スタックは、

int abd[7000]; /*過剰数リスト*/
int nums[28123 + 1];

できるほど大きくないので、グローバル変数にするなり、ヒープからとるなりしないと、
なんらかの実行時エラーがでても、不思議ではありません。

　で、グローバル変数にして実行したところ、abd が 7000 を超えたので、
adb も nums も一ケタ増やしてみました。

コード:

//
//
//
#include <stdio.h>


int 
isAbundantNumber(int x){
    int sum = 0;

    for(int i = 1; i < x; i++){
        if(x % i == 0){
            // printf("%d\n", i);
            sum += i;
        }
    }
    // printf("%d\n", sum);
    if(sum > x){
        // printf("YES\n");
        return 1;
    }

    return 0;
} 


const int adbMAX = 70000;
const int numsMAX = 281230;
int abd[ adbMAX ];  /*過剰数リスト*/
int nums[ numsMAX + 1 ];


int
main()
{
    int cnt = 1;
    int ans = 0;
    int i, j, a, b;

    // 配列初期化
    for(i = 0; i < adbMAX; i++){
        abd[i] = 0;
    }
    for(i = 0; i < numsMAX + 1; i++){
        nums[i] = 1;
    }

    // 過剰数リストをつくる
    for(i = 1; i <= 28123; i++){
        if(isAbundantNumber(i)){
            // printf("abd[%d] = %d\n", cnt, i);
            abd[cnt] = i;
            cnt++;
        }
    }
    // 2つの過剰数の和で書き表せない正の整数の総和を求めよ.
    for(i = 1; i < cnt; i++){
        printf( "Line%d: %d %d\n", __LINE__ , i, abd[i] + abd[j] );
        for(j = i; j < cnt; j++){
            nums[abd[i] + abd[j]] = 0;
        }
    }

    for(i = 0; i < 28123 + 1; i++){
        printf( "Line%d: %d, %d\n", __LINE__,  i, nums[ i ] );
        ans += i * nums[i];
    }

    printf("ans = %d\n", ans);

    return 0;
}


// end.

ans = 4179871

https://www.onlinegdb.com/
C++ 17 モード
で確認。

返信ありがとうございます。abdとnumsをグローバル変数にして要素数を10倍し、正しい答えが出ました。ありがとうございます！最終的なコードは以下のようになりました。皆さんありがとうございました。

コード:

#include <stdio.h>

int abd[70000];  /*過剰数リスト*/
int nums[281230];

int isAbundantNumber(int x){
    int sum = 0;
    for(int i = 1; i < x; i++){
        if(x % i == 0){
            // printf("%d\n", i);
            sum += i;
        }
    }
    // printf("%d\n", sum);
    if(sum > x){
        // printf("YES\n");
        return 1;
    }
    return 0;
} 

int main(){

    int cnt = 1;
    int ans = 0;
    int i, j, a, b;

    // 配列初期化
    for(i = 0; i < 7000; i++){
        abd[i] = 0;
    }
    for(i = 0; i < 28123 + 1; i++){
        nums[i] = 1;
    }

    // 過剰数リストをつくる
    for(i = 1; i <= 28123; i++){
        if(isAbundantNumber(i)){
            // printf("abd[%d] = %d\n", cnt, i);
            abd[cnt] = i;
            cnt++;
        }
    }

    // 2つの過剰数の和で書き表せない正の整数の総和を求めよ.
    for(i = 1; i < cnt; i++){
        // printf("%d\n", i);
        for(j = i; j < cnt; j++){
            // printf("%d, %d, %d, %d, %d\n", i, j, abd[i], abd[j], abd[i] + abd[j]);
            nums[abd[i] + abd[j]] = 0;
        }
    }

    for(i = 1; i < 28123 + 1; i++){
        // printf("%d, %d\n", i, nums[i]);
        ans += i * nums[i];
    }

    printf("ans = %d\n", ans);
    return 0;
}

プログラマ専用SNS ミクプラ

for文が途中で止まってしまう

for文が途中で止まってしまう

Re: for文が途中で止まってしまう

Re: for文が途中で止まってしまう

Re: for文が途中で止まってしまう

Re: for文が途中で止まってしまう

Re: for文が途中で止まってしまう