2^i * 3^j * 5^k なる整数 in C DouKaku?

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

何も考えずに。

#include <stdio.h>

int main(){
    int m=1;
    int n=0;
    int i,j,k;
    int v;
    
    do{
        v=m;
        i=0;
        j=0;
        k=0;
        while(v%2==0)v/=2,i++;
        while(v%3==0)v/=3,j++;
        while(v%5==0)v/=5,k++;
        if(v==1){
            printf("%d = 2^%d * 3^%d * 5^%d\n",m,i,j,k);
            n++;
        }
        m++;
    }while(n<100);
    return 0;
}

よく考えたら2で割るのにループはいりませんね。
i,j,kも省いてこんな感じかな。

#include <stdio.h>

int main(){
    int m,n,v;
    
    for(n=0,m=1;n<100;m++){
        v=m/(m&-m);
        while(v%3==0)v/=3;
        while(v%5==0)v/=5;
        if(v==1){
            printf("%d\n",m);
            n++;
        }
    }
    return 0;
}

DouKaku?

2^i * 3^j * 5^k なる整数

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq