1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
코드
n = int(input())
arr = map(int, input().split())
prime = [True] * 1001
prime[1] = False
# 에라토스테네스의 체
for i in range(2, int(1000 ** 0.5) + 1):
if not prime: # 이미 지워진 수
continue
for j in range(i * 2, 1001, i):
prime[j] = False # 자기자신을 제외한 배수들 지우기
ans = 0
for num in arr:
if prime[num]:
ans += 1
print(ans)
- 에라토스테네스의 체
에라토스테네스의 체 (소수 판별 알고리즘)
에라토스테네스의 체는 소수를 판별하는 알고리즘이다. 2 이상의 수에 대해 소수를 판별할 때 사용할 수 있다. 어떻게 하는지 단계별로 알아보자면 다음과 같다. 2부터 소수를 구하고자 하는 구
zero0205.tistory.com
'문제풀이 > 수학' 카테고리의 다른 글
[Python/파이썬] 백준 5347번 LCM (0) | 2023.02.06 |
---|---|
[Python/파이썬] 백준 2581번 소수 (0) | 2023.02.06 |
[Python/파이썬] 백준 1110번 더하기 사이클 (0) | 2023.02.05 |
[Python/파이썬] 백준 11653번 소인수분해 (0) | 2023.02.05 |
[Python/파이썬] 백준 1934번 최소공배수 (0) | 2023.02.05 |