백준 1978 : 소수 찾기

1978번: 소수 찾기

소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4
1 3 5 7

예제 출력 1

3

내 풀이

import sys

# 예제 입력 1
# 4
# 1 3 5 7

# 입력을 read()를 통해 전부 받고 split으로 구분하여 배열로 만듦
input = sys.stdin.read().split() 
# 입력에서 첫번째 줄(첫번째 요소)은 요소의 개수이므로 num이라는 변수에 할당해주었다.
num = input[0]
# 첫번째 요소를 제거한다.(이제 사용할 필요가 없으므로)
input.pop(0)
# 변수 이름을 직관적으로 설정해주기위해 이렇게 새로운 변수에 할당해주었다.
nums = list(map(int, input))
# print(nums)
count = 0

# 두번째 줄을 배열로 만든것을 순회함
for num in nums:
    if num == 1:
        continue
    else:
        # nums의 각 요소보다 작은 수로 나누기 위해 새로운 배열을 만듦
        divideArr = list(range(2, num))
        # print(divideArr)
        # 나누어졌는지 확인하는 배열
        isDivided = []
        for i in divideArr:
            if num % i == 0:
                isDivided.append(True)
            else:
                isDivided.append(False)
            # print(isDivided)
        if(True in isDivided):
            continue
        else:
            count += 1

                
print(count)

이 문제는 입력이

• 첫번째 줄에는 테스트 케이스 개수
• 두번째 줄에는 테스트 케이스 → 즉 숫자들이 공백을 기준으로 여러개

이렇게 주어진다.

첫번째 줄에 있는 요소를 먼저 취득하고 pop을 통해 제거를 한다. 그 이유는 이제 필요없기 때문에 제거를 하여 남아있는 요소를 쉽게 활용하기 위해서이다.

count는 소수의 개수를 세기위한 변수이다.

그리고 남아있는 요소(즉, 테스트 케이스)를 for 문을 통해 순회하며 소수인지 아닌지 확인할것이다.

먼저 요소가 1이라면 continue를 통해 무시하도록 한다.

아닌 경우는 아래에 서술한 대로 진행한다.

먼저 divideArr 변수를 만들고 2부터 요소까지의 수로 채워진 배열을 만든어 할당한다. (이 배열은 나중에 요소와 나누어서 나누어지는지 확인하는데에 사용된다.)

그리고 이제 divideArr 를 순회하면서 요소와 나누어떨어지는지 확인하고자 한다.

여기서 좀 고민을 했던것이 divideArr 의 모든 요소와 나누어 떨어지지않아야 소수이다.

따라서 어떻게 모든 요소와 비교를 비교를 한 결과를 확인할 수 있을까를 고민하다가 boolean을 활용하고자 했다.

그래서 나누어떨어졌는지의 결과를 boolen으로 만들고 isDivided 배열에 넣어주었다.

isDivided 배열에서 나누어떨어진 경우가 하나라도 있다면 True 요소가 있을것이다.

True 요소가 있다면 소수가 아니므로 무시해주고

모든 요소가 False라면 소수이므로 count에 1을 더해주었다.

이 문제를 공부하면서 배운 내용

에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

배열 요소 제거

인덱스로 제거하는 법

리스트명.pop(인덱스)

값으로 제거하는 법

리스트명.remove(값)

remove의 문제점

반복문을 돌리면서 요소를 제거할때 부수효과

[python] list로 for문 돌면서 remove할때 주의할점

for 문을 배열을 기준으로 돌리면서 배열이 삭제가 되므로 제대로 순회가 되지 않는다.

for문 요소 바꾸기

temp = ['apple', 'banana', 'coke']

for i in temp:
    if (i == "coke"):
        temp[temp.index("coke")] = "grape"
        #temp.index("coke")는 temp에서 "coke"를 찾아요.
        #해당 값이 있다면 그 값의 위치를 반환해준답니다.

print(temp)