[백준] Bronze 2. 1978 - 소수 찾기 python

문제 링크

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

---

문제 설명

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

 

입력

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

 

출력

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

---

제출 코드

import sys
import math

input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().split()))
result = 0

def isPrime(n):
    if n == 1:
        return False
    # 2부터 제곱근까지 모든 수 확인
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
    
for num in nums:
    if isPrime(num):
        result += 1

print(result)

 

풀이

• N은 100 이하, 주어지는 N개의 수는 1000 이하의 자연수로 크지 않다. for 문으로 확인해주자.
• 소수 여부를 판별하는 isPrime 함수를 만든다.
  • 2부터 제곱근+1 까지의 수에 대해 나누어 떨어지는지 확인한다.
  • 하나라도 나누어 떨어진다면 소수가 아니므로 False 리턴. 나누어 떨어지는 수가 없다면 True 리턴.

알아둘 사항

• 1은 소수가 아니므로 1에 대해 if 문을 예외 처리를 해줘야 함.
• 탐색해야 하는 수가 많은 경우 에라토스테네스의 체 활용

2024.07.11 - [coding test/알고리즘] - [python] 소수(Prime Number) 구하기 / 에라토스테네스의 체

[python] 소수(Prime Number) 구하기 / 에라토스테네스의 체