ページ

2012/09/13

[競技プログラミング][PHP][天下一プログラマーコンテスト2012]与えられた数より小さい素数の個数について

A - 与えられた数より小さい素数の個数について

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。
n
自然数 n ( 1≤n≤10,000 ) が 1 行で与えられる。

出力

n よりも小さい素数の個数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

出典

A: 与えられた数より小さい素数の個数について - 天下一プログラマーコンテスト2012 予選C | AtCoder

回答

AtCoder/tenka1_2012_C_1.php at master · wada811/AtCoder · GitHub
<?php
fscanf(STDIN, "%d", $n);
$isPrime[0] = $isPrime[1] = 0;
for($i = 2; $i < $n; $i++){
    $isPrime[$i] = 1;
}
for($i = 0; $i < $n; $i++){
    if($isPrime[$i] === 1){
        for($j = 2 * $i; $j < $n; $j += $i){
            $isPrime[$j] = 0;
        }
    }
}
$count = array_count_values($isPrime);
echo max(0, $count[1]).PHP_EOL;
?>
AOJ/vol0/AOJ0009.cpp at master · wada811/AOJ
AOJでC言語で書いた素数判定をPHPに書きなおすだけの簡単なお仕事。
array_count_valuesで素数フラグをカウントしてやればOKだけど
単純に出力すると2ケースだけテスト落ちる。
$n に 0 か 1 を渡されると出力するものがないので
maxで最低でも 0 を出力するようにするとちゃんと通る。