[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2004年予選>12問目

12問目(素数探し)

問題

6桁以下の正の整数nを入力し、n以下の素数がいくつあるかを数えて出力する

入力

n(整数)

出力

n以下の素数の個数(整数)

入力例

10

出力例

4

解き方例

エラトステネスのふるいで解きましょう。めんどくさいので説明はパスです。

ソースコード

お持ち帰り

C/C++

#include <stdio.h>

int main(){
    int n,in,count,i,j;
    char era[1000000];

    scanf("%d",&in);

    for(i=0;i<=in;i++){
        era[i]=1;
    }

    count=0;
    for(i=2;i<=in;i++){
        if(era[i] == 1){
            count++;
            for(j=i;j<=in;j+=i){
                era[j]=0;
            }
        }
    }
    printf("%d\n",count);

    return 0;
}

その他

エラトステネスについては上の階層の方で説明します(2006-5-9まだ書いていません)。パッパと実装できるようにしておきましょう。


ページの一番上へ
前のページへ 一覧に戻る 次のページへ
初版2006-5-9
[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2004年予選>12問目