Stage_9 (기본수학2) 192번 소인수분해

 

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

#소수 판별 함수 사용(문제 1978번 참조)

 

def Prime (n):

  if n < 2: return False

  elif n==2: return True

  else:

    for i in range(2,int(n**0.5)+1):

      if n%i == 0 :

        return False

        break

    return True

 

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

 

for i in range(M, N+1):

    if Prime(i): print(i)

# 지난 1978번 소수 구하는 문제에 사용한 함수를 사용하면 시간 초과가 된다

# 어떤 수의 약수는 중심점을 기준으로 좌우에 있는 수가 곱해지는데 이를 이용해 어떤 수의 절반까지만 나눠지는 수가 있는지 검사한다

# 이때 절반만 사용하기 위해 제곱근(루트)을 사용한다. 자세한 설명은 하기 링크 참조

 

coder38611.tistory.com/71

[백준 1929번-파이썬/Python] 소수 구하기