53631


コーディングテストの練習サイトCodilityの[CountSemiprimes](https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_semiprimes/)という問題を解いています。  
[CountSemiprimesについて日本語で書かれた記事](http://codility-lessons-
jp.blogspot.com/2015/03/lesson-9-countsemiprimes.html)

書いたコードを実行したところ、以下のエラーが出たため、出力の正しさを確認することができていません。  
どのように修正するべきでしょうか。

[code]

    Compilation successful.
    
    Example test:    (26, [1, 4, 16], [26, 10, 20]) 
    TIMEOUT ERROR  (running time: >5.00 sec., time limit: 5.00 sec.) 
    
    Detected some errors.
    
[/code]

書いたコード

[code]

    import itertools
    import math
    
    def solution(N, P, Q):
        #素数の配列を作成
        all = []
        nonprime = []
        for i in range (2, round(N/2)+1):
            all.append(i)
            #素数かどうか
            for m in range(2, int(math.sqrt(i))):
                if i % m == 0:
                    nonprime.append(i)
        prime = set(all) - set(nonprime)         
    
        #semiprimeの配列を作成
        semiprime = []
        #全ての２つの組み合わせを作成し、かけ算をしてN以下のものを配列に追加
        possible = list(itertools.combinations(prime,2))
        for j in range (len(possible)):
            pairs = possible[j]
            num = pairs[0] * pairs[1]
            if num <= N:
                semiprime.append(num)
    
        #P[]とQ[]の配列の範囲にあるsemiprimeの数を数える
        result = []
        for l in range(len(P)):
            count = 0
            for k in range(len(semiprime)):
                while semiprime[k] >= P[l] and semiprime[k] <= Q[l]:
                    count += 1
            result.append(count)
    
        return result 
    
[/code]


CC BY-SA 4.0
2019-03-21T14:25:51.003
53630
2019-03-22T00:26:40.920
2019-03-22T00:26:40.920
question
python python3 アルゴリズム
コードのタイムアウトエラーの修正方法について


記載されたコードに以下のような実際に実行する部分を追加して、

[code]

    def main():
        print(solution(26, [1, 4, 16], [26, 10, 20]))
    
    
    if __name__ == "__main__":
        main()
    
[/code]

実際に確認した結果、`while semiprime[k] >= P[l] or semiprime[k] <= Q[l]: count +=
1`の部分でループしていました。ループ判定条件に対応する部分が変動していないため、無限ループになっているようです。この部分を修正してください。


CC BY-SA 4.0
2019-03-21T14:57:15.803
53631
2019-03-21T14:57:15.803
29826
53630
answer