1

久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。

問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。

何が原因で、その解決方法はないのでしょうか?
わかる方、いましたら教えてください。

なお、コードは以下のとおりです。

import sys

def prime_calc(n):
    if n < 2:
        return False
    else:
        i = 2
        while n > i:
            if n % i == 0:
                return False
            else:
                i += 1
    return True

def prime(n):
    cnt = 0
    for i in range(0, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1
    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()

追記:
Fumu 7さんの解法を使ったのですが、それでもTime Limit Exceededと表示され、入力例を試しても、正しい数値にならず以下のような数値になってしまいます。

9
2
10

一体、何が原因なんでしょうか?

ちなみに、Fumu7さんの解法を使ったコードは以下のとおりです。

import math
import sys

def prime_calc(n):
    if n < 2:
        return False
    elif n==2 or n==3 or n==5 or n==7:
        return True
    else:
        rootN = math.floor(math.sqrt(n))
        i = 11
        while rootN > i:
            if n % i == 0:
                return False
            else:
                i += 2

    return True

def prime(n):
    cnt = 0
    for i in range(2, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1

    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()
8
  • 1
    入力待ちになったままタイムアウトしている様に見えますが…
    – user39889
    Commented 2018年7月4日 8:14
  • もしかしたらそうかも知れません…でもなんで入力待ちになったのでしょうか?前回やったときはそんなことなかったのですが?
    – Nagkei10
    Commented 2018年7月4日 8:28
  • 3
    ちなみに出入力に問題があるかどうかは同じ入力で間違った(てきとうな)答えを出すようなコードで wrong answer になるか TLE になるかで確かめるのがおすすめです.
    – Yosh
    Commented 2018年7月8日 10:59
  • 1
    prime_calc 関数の引数 n が文字列型ですので、math.sqrt(n)range(2, n, 2) でエラーになってしまいます。
    – user39889
    Commented 2018年7月17日 9:55
  • 1
    元になってる質問の内容が完全に変わってるので追記分は別の質問にされたほうがよいとおもいます.
    – Yosh
    Commented 2018年7月17日 10:09

5 件の回答 5

5

原因

確かに質問者さんのプログラムは Time Limit Exceeded (TLE) となります。これはアルゴリズム部分の実行が遅いためです。特に、各入力に対して毎回試し割りして素数判定を行っていることが実行時間を嵩ませています。

原因の割り出し方

まず、Yosh さんのコメントにあるように main 関数内の print(prime(line))print(42) に変えると Wrong Answer (WA) になるため、入出力が極端に遅いわけではないと分かります。TLE の原因はアルゴリズム部分にあります。

次にアルゴリズム部分を高速化するため、素数判定部分の試し割りを高速化できないか試してみましょう。ある正の整数 n が素数なのかどうか小さい数から順番に試し割りするようなプログラムは、次の事実を使って繰り返しの数を減らすことができます。

  • 偶数の素数は 2 のみである。
  • n が素数かどうかは、math.sqrt(n) までの自然数で割り切れるかどうか調べればよい。

このことを使うと、n が素数かどうか調べる関数 is_prime(n)このコードのように書けます。これで n が素数かどうか O(√(n)) の時間で判定できるようになりました。

今回の問題は n 以下の素数の個数を答えるものなので、素数判定を n 回実行したあと結果を足し合わせる必要があり、全体で O(n√(n)) の時間がかかります。データセットの数を Q、与えられる n の最大値を N とすると、データセット全てを処理するには O(Q × N√(N)) の時間がかかるということになります。

それなりに高速化できましたが、実はこれでもまだ TLE します。更に高速化が必要なようです。

更なる高速化

注意: ここから下には、AOJ 0009 の回答ネタバレが含まれます。

もう少し高速化してみましょう。よく考えると、ある数が素数かどうかの判定は最初に 1 回だけ行えばよいことに気づきます。素数判定の結果をメモしておけば、それぞれのデータセットに応じて毎回素数判定する必要はありません。

要するに、こうすればよいです。まず n の最大値 N = 999999 までそれぞれ素数判定し、次に各 n に対して答えがいくつなのかを全て計算してリストに覚えておきます。あとは与えられたデータセットごとに答えをそれぞれ出力すれだけです。

このようにすると、最初に一回だけ最大値 N まで素数判定をし、あとはデータセットの個数 Q の分だけ出力をすればよいです。こうすると全体の計算量は O(N√(N) + Q) となり、高速化できます。

ここまで高速化すると、TLE にならなくなります (実際のコード)。

また、実は更に高速化できます。素数判定部分で、それぞれの n について試し割りするかわりにエラトステネスのふるいを使えばよいです。実際 AOJ 0009 の Solution の多くはこの形で実装されています。

3
  • 1
    ちょっと出遅れたのでボソボソと、**で乗数が超えてるか比較すればmathを使わず済みます。
    – user10259
    Commented 2018年7月9日 8:49
  • N=10^6の時、N√N=10^9となり、実際にこれほどのステップ数が必要なら制限時間にはまず間に合わないと思います。TLEにはなっていないということなので、見積もりが緩すぎるのではないでしょうか?
    – letrec
    Commented 2018年7月9日 8:58
  • @letrec さん、それはそうですね。あくまで計算量の上限の漸近記法なので、実際の実行時間の目安にするつもりはありませんでした。素数定理を使えばより厳しい見積もりをすることができるでしょうが、それを解説すると回答が無駄に長くなるため、今回は避けることにします。
    – nekketsuuu
    Commented 2018年7月9日 9:10
3

素数の性質を使っていないので、無駄が多いと思います。

1)nの約数は、√n (ルート n)を超えることはない(1,000,000の最大の約数は、高々1,000)
という性質を使えば、

def prime_calc(n):
    if n < 2:
        return False
    else:
        i = 2
        while n > i:
            if n % i == 0:
                return False
        else:
            i += 1
return True

を以下のように修正できて、whileループの回数を n から (√n)/2 に抑えられます。
nが最大の999,999だった場合は、ループ回数(ほぼ実行時間に比例する)が2000分の1まで減ります。どんなinputが与えられるかに依存しますが、実行時間を2桁程度減らせるのではないかと思いますから、1秒以内に収まる可能性が高くなります。

import math
def prime_calc(n):
    if n < 2 :
        return False            
    elif n==2 or n==3 or n==5 or n==7: #設問にあるヒント、"例えば 10 以下の素数は、2, 3, 5, 7 です"を使いました。
        return True
    else:
        rootN = math.floor(math.sqrt(n))
        i = 11
        while rootN > i:
            if n % i == 0:
                return False
            else:
                i += 2 
       return True
2
  • Fumu7さん、あなたの解法は頼りになりますが、小さな数字のとき2以上は常に素数だと判定されてしまう上に肝心の999,999では時間がかかってしまいます。これでは素数判定のプログラムとしては成立しないではありませんか。お願いですから、修正してくれませんか?
    – Nagkei10
    Commented 2018年7月7日 6:48
  • その証拠となるソリューションです。Time Limit Exceededの原因はどこにあるか教えてください。judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3008140#2
    – Nagkei10
    Commented 2018年7月8日 8:05
2

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

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)])
0
1

私はAIZU ONLINE JUDGEを試したことがありませんが、for line in sys.stdin:は他の回答例でも使われていますので、コードは動作しておりCPU時間9:99でタイムアップ(目標1秒以内)となっている前提で記述します。

渡される複数のデータセットを配列lに登録し、個々の要素について個別に0からその数値までエラトステネスの篩を掛けているのがCPU時間を消費する要因として目につきます。

例えばデータセットが[3, 5]と入力された場合に、提示されたコードでは

  1. 最初の要素で3までの素数をカウントするため、0~3まで4回ループを回してそれぞれの値をprime関数に渡して素数計算をする
    prime関数は下記の動作を行う
    1. prime_calc(0)を呼び出してFalseを返す
    2. prime_calc(1)を呼び出してFalseを返す
    3. prime_calc(2)を呼び出す
      prime_calc関数は下記の動作を行う
      1. 2は素数なのでTrueを返す
    4. prime_calc(3)を呼び出す
      prime_calc関数は下記の動作を行う
      1. 2は素数なのでTrueを返す
      2. 3が素数か判定するため、1回ループを回してTrueを返す
  2. 5までの素数をカウントするため、0~5までループを回して上記の処理を行う

データセットの個数は30個まで、値は(1 ≤ n ≤ 999,999) ですので、個数や値が大きいと計算回数が非常に多くなります。

下記の観点から計算回数を減らすよう、コードを見直してみてください。

  1. ループの回数を押さえる
    例えば配列lに登録される数値が[5, 10, 10]の場合には、まず最小値である5以下の素数が[2,3,5]の3個であることを計算して、個数を変数に保存しておきます。
    次に6~10の素数が[7]の1個であることを計算します。上記の変数と個数を合計して10以下の素数の個数を求めて変数に保存します。
    最後に3つ目の要素10以下の素数は既に計算済みですので、計算をせずに4を返します。
  2. 無駄なループをしない
    0,1は素数ではないので、range(0, n+1):range(2, n+1):のように書き換えてループの回数を減らします。
  3. ループの回数を減らす
    4,6,8...といった2の倍数に対して素数判定をスキップすると、ループの回数が1/2に減ります。

素数計算の高速化にはこれ以外にも手法がありますが、まずは速度が遅くなる原因の計算回数を省略するためにロジックを見直すことで解決方法を検討してはいかがでしょうか。

1

皆さんが回答されているように、エラトステネスのふるい、をつかうのが適切なようです。
下記のコード(データセットの読み込みと、回答の出力の手前まで)で、実行時間は 0.355273962020874 秒でした。python 3.6.4、 PCは(Window10, CPU:core i7-3770 3.4GHz, Ram:8GB)を使用。

エラトステネスのふるいのための初期設定で、0,1,0,1,0,0 のパターンを追加していく(4+6nから始まる6つの数字は、「偶数、不明、偶数、不明、偶数、3の倍数」となることを利用)のが許されるかどうか微妙かもしれませんが、ループ回数が減って実行速度短縮に効果がありました。

import sys
import math
import time

start=time.time()

primes=[0,0,1,1] # 0,1は素数ではない、2,3は素数
for i in range (166666):
    primes += [0,1,0,1,0,0] # 4以降は、2の倍数、不明、2の倍数、不明、2の倍数、3の倍数、のパターンを繰り返す
print(len(primes))

#エラストテネスの篩(ふるい) 2と3の倍数は処理済みなので、5以降の素数でふるい
for j in range(5,1000,1):
    if primes[j]==1: #素数なら
        for k in range(2,math.floor((1000-j)/j),1):
            primes[j*k]=0 #その倍数を素数から外す

primesCount = [0,0,1,2] #
primesCountAcc = 2
for j in range(4,1000000,1):
  primesCountAcc += primes[j]
  primesCount += [primesCountAcc]

print("Elapsed time:",time.time()-start," seconds") #所要時間
#データ確認
print("数: 素数なら1 - 数以下素数の数")
for j in range(30): 
    print (j," : ",primes[j],"-",primesCount[j])

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。