[백준] 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)

소수 유형

# 1. 소수 판별(에라토스테네스의 체) > True or False
def is_prime(n) :
    prime = [False,False]+ [True] * n;
    for i in range(2, int((n+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, n+1, i):
                prime[j] = False;
    return prime;
# 2. n까지의 소수 목록 산출
def get_prime(n):
    prime = [False,False]+ [True] * n;
    for i in range(2, int((n+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, n+1, i):
                prime[j] = False;
    return [k for k in range(2,n) if prime[k] == True];