素数 再帰関数

質問

メイン
#include<stdio.h>
extern void count_primes(void);
extern void print_primes(void);
int max;
int count;
int primes[1000]
int main(void)
{
printf("Uper limit: ");
scanf("%d",&max);
count_primes();
print_primes();
}
素数を求める（関数呼び出し）
extern int nextprime(int n);
extern int max;
extern int count;
extern int primes[];
void count_primes(void)
{
int i;
count=0;
for(i=2;i<=max;i=nextprime(i)){
primes[count++]=i;
}
リカーバシブ（次の素数）
int nextprime[int n]
{
int i;
for(;;){
n++;
for(i=2;i*i<=n;i=nextprime(i)){
if(n%i==0)
break;
}
if(i*i>n)
break;
}
return n;
}
素数プリント
#include<stdio.h>
extern int count;
extern int primes[];
void print_primes(void)
{
int i
for(i=0;i<count;i++){
if((i>0)&&(i%10==0)
printf("\n");
printf(" %6d",primes[i]);
}
printf("\n素数の数　%d\n",count);
}
これら４つのモジュールで素数　nが求められますがアルゴリズム理解できません。この２つの関数のアルゴリズムについて、ご教授ください。め

回答No.3

επιστημη（@episteme）

int nextprime(int n) {
　int i;
　for(;;){
　　n++; /* 次の素数候補 */
　　/* i: 2から始めて√nを超えない範囲で */
　　for(i=2;i*i<=n;i=nextprime(i)){
　　　/* nがiで割り切れたならnは素数でない */
　　　if(n%i==0)
　　　break;
　　}
　　/* 上のループを抜けたとき i*i > n であったなら
　　 * nを割り切るiがなかった、すなわちnは素数である。
　　 * 素数が見つかったので無限ループを抜ける */
　　if(i*i>n)
　　　break;
　}
　return n;
}

お礼

大変分かりやすい説明ありがとうございました。
初心者の故一度迷いだすと、なかなか解決できませんでしたが、よく理解できました。有難うございました。

回答No.2

επιστημη（@episteme）

> void count_primes(void)とint nextprime[int n]との
> アルゴリズムを知りたいのですが！！

何がわからんのですか?

count_primes():
nextprime(i)がiより大きな最小の素数を返すので、
それを配列に格納しているだけ。

nextprime[int n]:
nextprime(int n) のマチガイでしょう。
「n が √n より小さなすべての素数で割り切れなければ n は素数である。」
を忠実に実装しています。

補足

nextprime(i)がiより大きな最小の素数を返すので、
それを配列に格納しているだけの説明を順を追ってご説明願います。

丸っきりの初心者です。”nextprime(i)がiより大きな最小の素数を返す”nの小さい数から順を追ってcount_primes()との関係をまじえてご説明ねがいたいのですが、無限ループでbreak文が２つ出てきたときの処理がわかりかねてます。この例題でいくn%i==0にならない限りつぎのif(i*i>n)への処理は行かない物と考えていますが、その前のfor文のnとiが限定されておりそこまでnとiがいかない場合はどうなるのでしょうか。
完全に頭が混乱しています順を追って説明していただければ幸いです。

回答No.1

επιστημη（@episteme）

わからないのは "リカーシブ（次の素数）"だけですよね?
# リカーバシブ は誤り

n が √n より小さなすべての素数で割り切れなければ n は素数である。

を忠実に実装しています。

補足

void count_primes(void)とint nextprime[int n]とのアルゴリズムを知りたいのですが！！