[기본수학 2] 소수 찾기
2021. 3. 12. 12:23ㆍ백준
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
시간 절약을 위해 10 이하 소수를 배열에 넣고 시작했다.
소수 (수론)
위키백과, 우리 모두의 백과사전. 좌측은 소수, 우측은 합성수. 소수란 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime nu
ko.wikipedia.org
from sys import stdin
import math
test_count = int(stdin.readline())
test_case = list(map(int, stdin.readline().split(" ")))
# 확인할 소수 갯수
pn_count = 0
# 10 이하 소수 리스트 (시간절약을 위해)
pn_list = [2, 3, 5, 7]
def check_prime_no(no: int):
# 1,0 이면 제외
if no == 1 or 0:
return False
# 이미 소수 리스트에 속한 요소면 소수
if no in pn_list:
return True
# 2 ~ n^1/2 + 1 구간에서 나눠서 0으로 떨어지는 수가 있는지 검증
for j in range(2, math.ceil(math.sqrt(no)) + 1):
if no % j == 0:
return False
# 없으면 소수니까 소수 리스트에 넣고 참 반환
pn_list.append(no)
return True
for i in range(0, len(test_case)):
target = test_case[i]
if check_prime_no(target):
pn_count = pn_count + 1
print(pn_count)