[백준 1978] 소수찾기

⭐ 소스 코드

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이 1,000 이하의 자연수이므로 방법 1에서 prime_list로 소수의 목록을 유한개의 리스트로 만들었다. 37^2 = 1,369 (>1000)이므로 소수를 찾기 위해 소수 37 까지 필요하다고 결론을 내릴 수 있다.
소요된 시간 복잡도는 상수이다. => O(1)

방법 2는 N의 범위와 관련이 없는 소수 찾기 풀이 방법이다.
소요된 시간 복잡도는 n/2이므로 n 이다. => O(n)