Stage_8 (기본수학2) 1978번 소수 찾기

두가지 풀이법

 

첫번째, 입력된 숫자 별로 소수인지 판단

 

#백준's Stage9 (기본수학) 1978번 소수 찾기

# N = 1~1000까지의 자연수가 주어짐

# 주어진 숫자보다 작은 값들이 배수인지 확인

 

#Prime No.인지 체크하는 함수 작성

 

def Prime (n):

  if n < 2: return False

  elif n==2: return True

  else:

    for i in range(2,n):

      if n%i == 0 :

        return False

        break

    return True

 

#변수 Input

T = int(input())

N = list(map(int,input().split()))

cnt = 0

 

for i in N:

  if Prime(i) : cnt += 1

 

print(cnt)

 

두번째, 1부터 1000까지의 전체 소수를 구한 후 비교

 

#어떤 숫자의 배수의 리스트를 구하는 함수

def del_N(multi_N):

  result = [multi_N * i for i in range(1,1000//multi_N+1)]

  return result

 

#1부터 1000까지의 리스트 생성

Prime_N = range(1,1001)

 

#29까지 각 소수의 리스트 생성. 29보다 큰 소수인 31과 37는 두 곱이 1000을 넘어가므로 29까지 작성

multi_N = [2,3,5,7,11,13,17,19,23,29]

 

#1~1000의 리스트에서 각 소수의 배수들을 삭제

for j in multi_N:

  Prime_N = [x for x in Prime_N if x not in del_N(j)]

del Prime_N[0]

Prime_N = multi_N + Prime_N

 

#변수 Input

T = int(input())

N = list(map(int,input().split()))

 

cnt = 0

 

#전제 소수 리스트에서 입력된 값이 있는지 확인

for m in N:

  if m in Prime_N: cnt += 1

 

print(cnt)

 

 

## Comments : 두번째 방법으로 미리 전체 List를 구해 놓으면 속도가 더 빠를 것으로 예상하였으나 예상을 빗나갔다.

                     리스트에 어떤 값이 있는지 찾아보는 것이 생각보다 오래 걸리는 것으로 생각된다.