20210813#(79) 백준 1929번 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

이전에 실패한 문제에 있어서 풀어본 문제!

 

 

○ 풀이

import math

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

m,n = map(int,input().split())

for i in range(m, n+1):
  if isPrime(i):
    print(i)

 

 

○ 배운점

math 함수를 이용 제곱근만 계산하여 시간효율 up

import math

math.sqrt(n)  == n의 제곱근

 

 

○ 소수찾기할때 왜 제곱근을 기준으로 판별할 수 있는가? 

제곱근(sqrt) 범위 나누기법이란?  소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법입니다. 예). 18로 예를들면, 18의 약수는 1, 2, 3, 6, 9, 18이며, 18은 1 * 18, 2 * 9, 3 * 6   < √18 >   6 * 3, 9 * 2, 18 * 1입니다. √18  * √18도 18인데, 이 √18을 좌우로 곱하기가 대칭이므로 sqrt()값보다 같거나 작은 숫자로 나누어지면 그 이후에 대해서는 대칭이므로 계산을 할 필요가 없다는 원리로 검사하려는 수의 제곱근 값 이하의 수만큼 체크하면 되는 기법입니다. √18의 값은 4.2426... 이므로 4까지 나누어 떨어지지 않으면 소수가 아니라는 의미이며 큰 수도 몇번의 계산으로 확인가능하다는 장점이 있습니다. 출처: https://www.it-note.kr/308 [IT 개발자 Note]