[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)