소수 구하기 복습 [파이썬]

전에 에라토스테네스의 체를 공부했지만, 

그냥 개개별의 수에 대해서 원초적인 방식으로 문제를 접근했을 때 시간초과가 떠서 다른 방식을 검색해보다 알게 된 것이

바로 중간값을 이용한 방법이다. 

쉽게 설명하면, 16의 약수는 1,2,4,8,16 으로 4를 기준으로 양옆으로 퍼져있다. 

즉, 중간값을 기준으로 해당 약수의 갯수가 나란히 있다는 것이다. 이 방법을 바탕으로

 

import math


n = 7
cnt = 0
for i in range(2,int(math.sqrt(n)) + 1):
    if n % i == 0:
        a = False
        break
    else:
        a = True
print(a)

n = 7로 두고 소수인지 판별을 해보면 false 가 나오고 8로 하면 true가 나온다. math.sqrt(숫자) + 1 이걸 생각해서 나중에 소수구하기 문제를 풀 때 활용해야 겠다