728x90
문제 설명
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
예제 입력 1
4
1 3 5 7
예제 출력 1
3
풀이
# 소수 찾기
# 에라토스테네스의 체
# n < 1,000 이하의 자연수
import math
n = int(input())
num = list(map(int, input().split()))
cnt = 0
A = [i for i in range(1001)]
A[1] = 0
for i in range(2, int(math.sqrt(len(A)) + 1)):
if A[i] == 0:
continue
for j in range(i + i, len(A), i):
A[j] = 0
for i in range(n):
if A[num[i]] != 0:
cnt += 1
print(cnt)
- 에라토스테네스의 체를 이용하여 소수를 구한다.
- 전체 수가 1,000 이하의 자연수이므로 소수를 찾기 위한 A 리스트 길이를 1001로 설정한다.
- A는 인덱스와 값이 동일하다.
- for문을 돌면서 소수를 판별한다. 소수일 경우 0으로 값을 할당한다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 / 정수론] 11689 : GCD(n, k) = 1 (python) (0) | 2024.04.08 |
---|---|
[백준 / 정수론] 2609 : 최대공약수와 최소공배수 (python) (0) | 2024.04.08 |
[백준 / 소수] 1456 : 거의 소수 (python) (0) | 2024.04.05 |
[백준 / 그리디] 2839 : 설탕 배달 (python) (0) | 2024.04.04 |
[백준 / 그리디] 1931 : 회의실 배정 (python) (0) | 2024.04.04 |