BAEKJOON 1978 - 소수 찾기

BAEKJOON 1978 - 소수 찾기

---

◎ Problem Definition

1978번: 소수 찾기

---

◎ Implementation

1. Problem Type 

 - Implementation (Silver 4)

2. Problem Analysis

input : 1000 이하의 자연수 N개
output : N 개의 숫자 중에서 소수를 구한다. 

- ​입력값 중에서  max값을 찾아보자.

- max값까지 소수를 계산하자.

- 소수 list와 input list를 비교하여 겹치는 element의 개수를 구하자. 

3. Solution_1 (☆초기 접근)

1. 데이터를 set 형태로 선언하여 주어진 list 중 최대값까지 발생하는 모든 소수의 집합을 구한다. 

2. 1에서 계산한 소수 집합과 입력 집합 간 합집합을 구해 원소 개수를 출력한다. 

▶ 완성 코드

# backjoon #1978 : Find Prime Number

# inputs
N = int(input())
data = set(map(int, input().split())) 

# find prime numbers under N+1
num_list = []
n_max = max(data)
for n in range(2, n_max+1):
    k = n
    while k <= n_max:
        k += n
        num_list.append(k)

all = set(range(2,n_max+1))
nums = all - set(num_list)
# print(nums & data)
print(len(nums & data))

▶ 성능 

논리가 간단하여 나쁘지 않은 접근이라고 생각한다. 하지만, 중간에 불필요한 연산들이 많아서 element 간 분포가 큰 데이터에는 부적합하다. 

4. Solution_2 (☆공개된 다른 코드 참조)

▶ 완성 코드

##########################################
# TRIAL #2  
# reference : https://www.acmicpc.net/source/18191610
##########################################

# input 
N = int(input())
data = list(map(int, input().split()))
cnt = 0 
for n in data:
    flag = True
    if n <= 1:
        continue
    for i in range(2, n):
        if n % i == 0:
            flag = False
            break
    if flag :
        cnt += 1
print(cnt)

▶ 성능

두 번째는 주어진 element의 수가 적을수록 유리한 방법이다. 코드길이, 메모리, 시간 모두 두번째 접근이 더 효율적이다.

 

 

---

◎ Results

- print문 내부에

- 코딩 능