プログラムの計算量の表記について

[ひげが伸びた]

100以下の素数を全て画面に表示するプログラムを作りなさい．何を使っても良い．
そして、作成したプログラムの計算時間量はどのぐらいかをコメントとして
プログラムの最後に書き込みしなさい。

という課題が出ました。プログラムを作るのはできるのですが、計算時間量の求め方がわかりません。

この課題が出た講義で使ったのがO記法なので、これを使わなければならないと思います。

どういった具合にすれば求めることができるのでしょうか？
わかるかた、教えていただけると助かります。

[かずま]

O記法による時間計算量は、入力データの個数によって、
計算時間がどのように増加していくかを表すものです。

100以下の素数をすべて画面に表示するプログラムは、
入力データがないので、O(1) ではないでしょうか？

[ひげが伸びてきた]

#include <stdio.h>

int main(void)
{
int i,j,yaku;

for(i=1;i<=100;i++)
{
yaku=0;
for(j=1;j<=i;j++)
{
if(i%j==0) yaku++;
}

if(yaku==2) printf("%d ",i);
}

printf("\n");

return 0;
}


このようにプログラムを組んだんですけどこの場合のプログラムの計算時間量もそれでいいんですかね？？

[かずま]

n 以下の素数として、n が 100の場合、200の場合、1000の場合などとするなら、
その n に対して、計算量を求めることができます。

そのプログラムは、for文の二重ループで、どちらも nに比例する回数
回りますから、O(n²) でしょう。

[KRNKRS]

返答ではなく申し訳ないですが、
ソースコードはcodeで囲みましょう

コード: 全て選択

#include <stdio.h>

int main(void)
{
    int i,j,yaku;
    for(i=1;i<=100;i++)
    {
        yaku=0;
        for(j=1;j<=i;j++)
        {
            if(i%j==0) yaku++;
        }
        if(yaku==2) printf("%d ",i);
    }
    printf("\n");
    return 0;
}