[白俊1978]少数を探す

1058 ワード
テキストリンク

ソースコード
prime_list = [2,3,5,7,11,13,17,19,23,29,31,37]

# 방법 1) 시간 복잡도 O(1)

def prime(a):
    for i in prime_list:
        if a == i:
            return True
        if a % i == 0:
            return False
    return True


# 방법 2) 시간 복잡도 O(n)

def prime(num):
    for i in range(2, num//2 + 1):
        if num % i == 0:
            return False
    return True

if __name__ == '__main__':
    N = input()
    num_list = list(map(int, input().split()))
    cnt = 0

    for i in num_list:
        if i == 1:
            continue
        if prime(i):
            cnt += 1

    print(cnt)
解釈プロセス
問題ではNは1000以下の自然数であるため,方法1ではprimeリストで少数リストを有限リストにする.37^2=1369(>1000)なので小数を探すには小数37まで必要です.
所要時間の複雑さは定数です.=>O(1)

方法2はNの範囲に関係のない小数点探索解法である.
所要時間複雑度はn/2であるため、nとなる.=>O(n)
CSS背景-調整画像
1449-空港リフト-グリディアルゴリズムの修理