[백준] 1929번 : 소수 구하기
문제
느낀점
자료구조 책에 소수 나열하기 부분이 있었어서(p98) 총 세가지 방식으로 풀어봤다. 결국 에라토스테네스의 체를 이용한 마지막 풀이 방식이 시간초과가 나지 않았다. 이 부분은 솔직히 책으로 볼 때도 이해가 되지 않아 별표를 쳐뒀던 부분인데, 아직도 이해가 되지 않는다.
개념
에라토스테네스의 체 (이름은 중요하지 않을 듯)
소수는 해당 소수의 제곱근 이하의 정수로 나눴을 때 나누어 떨어지지 않으면, 소수이다.
첫번째 풀이
M, N = map(int, input().split())
for i in range(M, N+1):
for j in range(2, i):
if i % j == 0:
break
else :
print(i)
두번째 풀이
소수는 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다는 특성 활용
소수를 sosu 리스트에 저장시키고 해당 소수로만 나눗셈 실시
M, N = map(int, input().split())
ptr = 0
sosu = [2]
ptr +=1
for i in range(M, N+1, 2):
for j in range(len(sosu)):
if i % sosu[j] == 0:
break
else :
sosu.append(i)
print(i)
정답 풀이
# 소수는 소수의 제곱근까지 나눴을 때 나눠떨어지지 않으면 소수가 됨
M, N = map(int, input().split())
for i in range(M, N+1):
if i == 1:
continue # continue는 for문 if문 같은 곳에서 사용 시, 다음 루프로 넘기는 역할을 함
for j in range(2, int(i**0.5)+1):
# (2,int(i**0.5)+1, 2)로 하면 2,4 의 경우 2만 출력됨 (3을 건너뛰기 때문)
if i % j == 0:
break
else :
print(i)
Author And Source
이 문제에 관하여([백준] 1929번 : 소수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/백준-1929번-소수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)