[백준 1929] 소수 구하기 (Silver 3)

문제

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

접근

소수 알고리즘

• 해당하는 숫자의 중간값을 통해 소수 판별이 가능하다

  • 16의 약수들을 일렬로 나열하면 1, 2, 4, 8, 16이다
  • 16의 중간값 4를 기준으로 서로 대칭이다 (1 x 16 = 16 x 1, 2 x 8 = 8 x 2)
  • 즉, 16의 약수를 찾기 위해 싶다면 중간값을 기준으로 한 쪽만 검사를 할 수 있다.

• 중간값은 찾고자하는 수의 제곱근 값으로 가정해 처리할 수 있으며, 이 제곱근 값을 기준으로 왼쪽에 약수가 하나도 존재하지 않는다면 오른쪽에도 약수가 존재하지 않는다.

• 즉, 기존 소수 찾는 방법O(N^2)에서 연산을 반 이상 줄일 수 있다.

Code

import sys, math

n, m = map(int, sys.stdin.readline().split())

for i in range(n, m+1):
    if i == 1:
        continue
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            break
    else:
        print(i)