Skip to main content
コードの編集(i>は見る必要がない)
ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)

import sys

N = 10**6

is_prime = [True for _ in range(N)]

c = 0
count = [0 for _ in range(N)]

# sieve
p = 0
is_prime[0] = is_prime[1] = False

for i in range(2,N):
    if is_prime[i]:
        c += 1
        for j in range(i*2*i, N, i):
            is_prime[j] = False
    count[i] = c

for line in sys.stdin:
    print(count[int(line)])

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)

import sys

N = 10**6

is_prime = [True for _ in range(N)]

c = 0
count = [0 for _ in range(N)]

# sieve
p = 0
is_prime[0] = is_prime[1] = False

for i in range(2,N):
    if is_prime[i]:
        c += 1
        for j in range(i*2, N, i):
            is_prime[j] = False
    count[i] = c

for line in sys.stdin:
    print(count[int(line)])

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)

import sys

N = 10**6

is_prime = [True for _ in range(N)]

c = 0
count = [0 for _ in range(N)]

# sieve
p = 0
is_prime[0] = is_prime[1] = False

for i in range(2,N):
    if is_prime[i]:
        c += 1
        for j in range(i*i, N, i):
            is_prime[j] = False
    count[i] = c

for line in sys.stdin:
    print(count[int(line)])
具体的な情報を追加
ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)

import sys

N = 10**6

is_prime = [True for _ in range(N)]

c = 0
count = [0 for _ in range(N)]

# sieve
p = 0
is_prime[0] = is_prime[1] = False

for i in range(2,N):
    if is_prime[i]:
        c += 1
        for j in range(i*2, N, i):
            is_prime[j] = False
    count[i] = c

for line in sys.stdin:
    print(count[int(line)])

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)

import sys

N = 10**6

is_prime = [True for _ in range(N)]

c = 0
count = [0 for _ in range(N)]

# sieve
p = 0
is_prime[0] = is_prime[1] = False

for i in range(2,N):
    if is_prime[i]:
        c += 1
        for j in range(i*2, N, i):
            is_prime[j] = False
    count[i] = c

for line in sys.stdin:
    print(count[int(line)])
ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。