アドバイスお願いします

質問

今，以下の様なプログラムを作っています．
正の整数ｎを上限とする数字の集合を考える．
そのうち a*i+b*j で表現できない値の個数を出力する．
a,bは事前に与えられた正の整数であり，i,jは正の整数の変数である．
またa,b,nの取り得る最大値は1000000とする．

とりあえずfortranで総当たりの方法で作ってみました．

integer a,b,n,ans(1000000),c
read(*,*)a,b,n
　do i=1,n
　　ans(i)=i
　enddo
icount=0
do i=0,n
　do j=0,n
　　c=a*i+b*j
　　if(c.le.n)then
　　　do k=1,n
　　　　if(ans(k).eq.c)then
　　　　　ans(k)=-1
　　　　endif
　　　enddo
　　endif
　enddo
enddo
do i=1,n
　if(ans(i).gt.0)then
　　icount=icount+1
　endif
enddo
write(*,*)icount
end

ｎの値があまり大きくなければ問題なく動くのですが，
最大値である1000000を入力して走らすと，とんでもなく
時間がかかってしまいます．
もっとスマートな方法は無いものでしょうか？
アドバイスお願い致します．

回答No.3

BLUEPIXY · ベストアンサー

#2の補足について
10　　　enddo
　　enddo
は
　　　enddo
10　enddo
じゃないのでしょうか？

お礼

なんとお恥ずかしい(^_^;)
その通りですね．
指摘通り手直ししたら，あっけなく動いてくれました．
自分の未熟さを痛感しました．
まだまだ努力が足りないようです．
この度は質問に答えて頂きありがとうございました．

回答No.2

BLUEPIXY

＃１のプログラムについて
基本的な方針は、
a*i+b*j=kとなりうるkを1～nまで調べます。
条件からiが最大になるのは、
b=0の時で
imax=[k/a] ただし[]はガウス記号
なので、
iを0～imaxまで調べます
上記までの条件の時jが存在するかどうかは、
(k-a*i)がbで割り切れるかどうかです。
(k-a*i)%b==0は
(k-a*i)をbで割った時のあまりが０であるという意味です。
この時、kを表現するi,jが見つかったということなので、iのループを脱出し、次のkを調べます。
ans[k-1]は、Ｃでの配列が０から始まるためにずらしています。
=0は、=-1でもいいですが、機械語になった時判定が少しでも速くなればいいなという希望を込めて0でやっています。
*p++=1;も少しでも速く動けばいいなという意味です。

点検のために、表現できなかったkを表示していますが、これは、必要有りません。

フォートランで書ければ良かったのですが、
フォートランは読めますが、まともに書いたことがないので、Ｃで書いてみました。申し訳ないです。

補足

解説ありがとうございます．
やっと謎が解けました．

というわけで，早速fortranにて書き直してみました．
しかしn=1000000となると，前と同じく恐ろしく時間がっかってしまい，お手上げ状態です．
このプログラムに関してはfortranで無くてもよいのですが，
やはり，なぜうまくいかないのか気になります．
言語の違いだけで，ここまで差があるとは思えないのですが…

ちなみに以下がソースです．

　　integer a,b,n,ans(1000000),c
　　read(*,*)a,b,n
　　do i=1,n
　　　ans(i)=1
　　enddo
　　icount=0
　　do i=1,n
　　　imax=i/a
　　　　do j=0,imax
　　　　　if(mod(i-a*j,b).eq.0)then
　　　　　　ans(i)=0
　　　　　　goto 10
　　　　　endif
10　　　enddo
　　enddo

　　do i=1,n
　　　if(ans(i).eq.1)then
　　　　icount=icount+1
　　　　write(*,*)i
　　　endif
　　enddo
　　write(*,*)'kotae',icount
　　end

回答No.1

BLUEPIXY

とりあえず、Ｃで作ってみました。
それほど、スマートでもないですけど、
実用的な時間でできます。
#include <stdio.h>

#define MAX 1000000

static unsigned ans[MAX];

void main(void){
unsigned a,b,n,count=0;
unsigned i,k,*p,imax;
char buff[80];

printf("input a,b,n>");
gets(buff);
sscanf(buff,"%u,%u,%u",&a,&b,&n);
printf("a=%u,b=%u,n=%u\n",a,b,n);
for(i=0,p=ans;i<n;i++)
*p++=1;

for(k=1;k<=n;k++){
imax=k/a;
for(i=0;i<=imax;i++){
if((k-a*i)%b==0){
ans[k-1]=0;
break;
}
}
}
for(i=0;i<n;i++)
if(ans[i]){
count++;
printf("%u\n",i+1);
}
printf("個数：%u\n",count);
}
ところで、i,jは、正の整数ってことになってるけど
プログラムの方は、０を含むようになっているけど、それでいいんでしょうか？

補足

早速のお返事ありがとうございます．

＞ところで、i,jは、正の整数ってことになってるけど
プログラムの方は、０を含むようになっているけど、それでいいんでしょうか？

その通りです．ちょっとわかりずらかったようで(^_^;)

少し質問があるんですが
if((k-a*i)%b==0)
ここの条件判定がいまいち分からずにいます．
もしよろしければ解説おねがいします．