2.[1주차] baekjoon 1978번 파이썬 문제풀이+에라토스테네스의 체

백준 1978번 문제를 풀어보겠다.

문제는 위와 같다.

 

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다.

이를 판별하는 방법은 입력받은 숫자를 2부터 입력받은 수-1까지 나누어 보았을 때 나누어 떨어지면 소수가 아닌 것으로 찾는 방법과 에라토스테네스의 체 알고리즘을 사용하는 방법이 있다. 전자는 효율이 떨어지기 때문에(속도가 느림.) 후자를 기준으로 살펴본다.

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이고  N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

과정:

1. 2부터 N까지의 모든 자연수를 나열한다
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다
3. 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.

에라토스테네스의 체 시각화

import sys
input = sys.stdin.readline
N = int(input())

num_list = []

num_list=map(int, input().split())

prime_cnt=0

for i in num_list:
    #에리토스테네스의 체
    flag = 0
    if i > 1:
        for j in range(2, i//2+1):    
            if (i%j == 0):
                flag += 1 #배수는 배열에서 제거 
        if flag == 0:
            prime_cnt+=1 #배수가 아님 
print(prime_cnt)

여기서는 input() 말고 sys.stdin.readline을 input에 넣어 값을 입력받았는데 그 이유는 반복문으로 여러줄을 입력 받아야할 때 시간초과를 방지하기 위함이다.  이를 사용하기 위해 import sys를 선언해주었다.

잘 출력되는지 확인하고 제출해준다.

 

사실 에라토스테네스의 체가 어렵게 다가와서 효율이 떨어져도 N의 값이 100이하라 전자의 경우도 코드로 작성해보았다.

 

좌측에서 보이는 오류 마크는 띄어쓰기 관련 오류이다(구름ide에서 띄어쓰기 오류를 저렇게 표시해줌.) 위 상황에서는 주석 띄어쓰기 오류이므로 무시해도 된다. 

여태 풀었던 백준 문제에서와 같이 입력값을 받을 때 map(),split()을 사용했다.

 

숫자를 몇개 입력받는지에 대해서 변수 N으로 입력 받고, 그 이후에 입력하는 숫자들은 num 변수에 저장했다. 

for문을 사용하여 2부터  N-1까지의 수를 나누어 떨어지는지를 판별했다.

잘 출력되는지 확인하고 제출한다.

백준 1978번 문제는 이렇게 마무리하겠다.