용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

(Python) 백준 1978번 - 소수 찾기
알고리즘/알고리즘 문제 풀이

(Python) 백준 1978번 - 소수 찾기

2022. 12. 26. 01:16

문제 링크 : https://www.acmicpc.net/problem/1978

 

1978번: 소수 찾기

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

www.acmicpc.net

풀이

처음엔 단순하게 에라토스테네스의 체 방식으로 풀어서는 시간 초과가 날 수 있을거 같았으나 문제 분류에 에라토스테네스의 체라고 적혀있어서 시도해보았더니 제한 시간 내에 통과할 수 있었다.

n = int(input())
count = 0 # 소수가 아닐 경우를 count
arr = list(map(int, input().split()))
for num in arr:
    if num == 1:  # 1은 소수가 아님
        count += 1  # 소수가 아니면 count
    else:
        for div in range(2, num):
            if num % div == 0:  # 2부터 (자기자신-1)까지 한 번이라도 나누어 떨어지면 소수가 아님
                count += 1  # 소수가 아니면 count
                break
print(n - count) # 전체 경우에서 소수가 아닌 경우의 수를 빼면 소수인 경우의 수가 나옴

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

(Python) 백준 7568번 - 덩치  (0) 2022.12.28
(Python) 백준 2751번 - 수 정렬하기 2  (0) 2022.12.27
(Python) 백준 1436번 - 영화감독 숌  (0) 2022.12.25
(Python) 백준 1181번 - 단어 정렬  (0) 2022.12.24
(Python) 백준 10989번 - 수 정렬하기 3  (0) 2022.12.20
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • (Python) 백준 7568번 - 덩치
    • (Python) 백준 2751번 - 수 정렬하기 2
    • (Python) 백준 1436번 - 영화감독 숌
    • (Python) 백준 1181번 - 단어 정렬
    용꿀
    용꿀

    티스토리툴바