[99일차] 소수 찾기 - 백준 - 1978(python - 정수론, 소수 판정)

문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

예제 입출력

4 1 3 5 7

3

 

코드 및 설명

n = int(input())
n_arr = list(map(int, input().split(" ")))
answer = 0

for val in n_arr:
  tmp = []
  cnt = 1
  while True:
    if val < cnt:
      break
    else:
      if val % cnt == 0:
        tmp.append(cnt)              
      cnt += 1
    
  if len(tmp) == 2:
    answer += 1

print(answer)

 

이 문제는 소수의 개수를 구하는 문제이다. 소수란 약수가 1과 자기 자신만 있는 자연수를 소수라고 한다.

 

위의 코드는 입력받은 수들을 전부 확인하여 소수이면 answer+ 1를 하는 코드인데... 정답은 통과되나 자연수 1000개 조건

 

이 아닌 1000만개이면 시간초과가 될 것 같다. 좀 더 개선된 알고리즘을 사용해본다.

 

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

for val in n_arr:  
  check = primenum(val)
  
  if check:
    answer += 1 
          
print(answer)

 

위에 코드에 대한 설명을 예제로 해보겠다.

 

16이 소수인지 아닌지 판별하려면,

 

1 * 16

2 * 8

4 * 4

8 * 2

16 * 1

 

여기서 보면 2 * 8, 8 * 2가 결국 같은 건데 맨 위에 코드에선 이걸 다 돌게 된다. 4 * 4까지만 돌면 전부 확인이 된다는 것.

 

제곱근+1까지만 돌려주면 끝까지 확인하지않고 중복될 행위를 줄여줄 수 있게 된다. 

 

math.sqrt가 제곱근을 구해주는 함수이다. val % i == 0 나머지값이 0이 되면 소수가 아니기 때문에 false, 나머지값이 0이 

 

없으면 True로 반환된다. 1의 소수(http://allthatmath.com/bbs/board.php?bo_table=sub_113&wr_id=368)가 아니다.

 

1은 False, 나머지는 1 * 3, 1 * 5, 1 * 7 밖에 없으므로 소수가 된다. 그래서 답은 3으로 나온다.

 

이런 문제도 있을 수 있다. 1000까지의 소수를 구하라. 그럼 에라토스테네스의 체 알고리즘을 사용하면 된다.

 

이건 문제가 혹시 나오면 풀어서 올려보겠다.