[1978 – 파이썬] – 소수

처음 풀때 솔직히 어렵지는 않았는데…효율적이지 않다는 걸 깨달았습니다…

물론 첫 번째 반복문에서 num은 이전 숫자의 기본을 잊어버려서 멍청한 짓을 했습니다 ㅎㅎ.

첫 번째 해법은 0~1은 소수가 될 수 없으므로 넘기고 나머지 값은 루프문으로 나누면 소수가 아니고, 그렇지 않으면 아래의 if문으로 값을 얻는다. 그런데 여기서 문제는 숫자가 커질수록 그 숫자로 나누는 과정을 반복해야 한다는 점이다.

n = int(input())

nums = list(map(int, input().split()))
count = 0

for num in nums:
  result = True
  if num < 2:
    result = False
    pass
  else:
    for i in range(2, num):
      if num % i == 0:
        result = False
        break
  if result == True:
    count += 1 
    
print(count)

그래서 효율적인 방법을 찾아봤는데 역시나… 고대 그리스 수학자들은 이미 그 방법을 알고 있었다…

숫자의 제곱근까지만 나누어 불필요한 반복을 줄입니다.

n = int(input())

nums = list(map(int, input().split()))
count = 0

for num in nums:
  result = True
  if num < 2:
    result = False
    pass
  else:
    for i in range(2, int(num**0.5) + 1):
      if num % i == 0:
        result = False
        break
  if result == True:
    count += 1 
    
print(count)