[백준(python)] 1929번: 약수의 합

1929번: 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이 (시간초과)

def isPrime(n):
    if n == 1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

numList = list(map(int, input().split()))

for n in range(numList[0],numList[1]+1):
    if isPrime(n) == True:
        print(n)

설명

가장 간단하게 소수 판별식을 사용해서 작성하면 시간초과가 뜬다
약수는 대칭성을 갖고있다 는 특징을 이용.

정수n을 루트n만큼의 순회만으로도 약수를 세는 것이 가능함

즉, 정수 6의 약수 중에는 3이 존재하는데
6/3인 정수2 또한 6의 약수가 됨

맞는 풀이1 (4880ms)

def primality(n):
    if n == 1:
        return False #1은 소수가 아님은 자명함
    i = 2
    while i * i <= n: #n번 순회하지 않고 루트n만큼만 돈다는 뜻과 같음
        if n % i == 0:
            return False
        i += 1
    return True

M, N = map(int, input().split())

for n in range(M,N+1):
    if primality(n) == True:
        print(n)

맞는 풀이2 (5236ms)

#import math

M, N = map(int, input().split())

for n in range(M,N+1):
        have = 0 #n이 약수를 갖고있는지 판별하는 변수
        if n > 1:
            for i in range(2, int(n**0.5)+1): #int(math.sqrt(n))을 사용해도 가능
                if n % i == 0:
                    have += 1
                    break
            if have == 0:
                print(n)

맞는 풀이3 (296ms)

M, N = map(int, input().split())
N += 1 # N의 값을 아예 + 1 해줘버림!!
arr = [True] * (N) # memoization 사용. 우선 다 소수라고 초기화
arr[1] = False # 1은 소수가 아니니까 False

for i in range(2, int(N**0.5)+1):
    if arr[i] == True:  # 소수라고 적혀있는 것의
        for j in range(2*i, N, i): # 배수들은 arr[i]를 약수로 가진다는거니까
            arr[j] = False # 소수가 아니라고 바꿔주기
            
# 위의 for문을 다 하고나면 arr에 소수인지 아닌지에 따라 true혹은 false가 들어있음.

for i in range(M, N):
    if arr[i] == True: # true 즉, 소수인 것들만 출력
        print(i)