[알고리즘_07] 백준 1978번 소수 찾기

공부 포인트: 컴퓨팅 사고

 

문제

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

 

입력

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

 

출력

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

 

 

알고리즘

N = int(input())
A = list(map(int, input().split()))

#소수의 개수
result = 0

for i in A:
    cnt = 0

    if i == 1:
        continue

    for j in range(2, i+1):
        if i % j == 0:
            cnt += 1

    if cnt == 1:
        result += 1

print(result)

 

알고리즘 설명

주어진 숫자 중 소수가 있는지 없는지 찾는 문제입니다.
소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
1을 제외하면 자기 자신만을 약수로 가진다는 뜻이네요.

2~자기 자신까지 차례로 나눴을 때 나누어 떨어지는 수가 자기 자신 하나뿐입니다.

7을 예로 들면
7 % 2 = 1
7 % 3 = 1
7 % 4 = 3
7 % 5 = 2
7 % 6 = 1
7 % 7 = 0
나누어 떨어지는 수가 1개 이므로 7은 소수입니다.

코드를 순서대로 작성한다면
1. 주어지는 수를 입력
2. 소수의 갯수를 셀 변수를 선언
3. 주어지는 수를 하나씩 대입
    3-1. 나머지가 0인 갯수를 셀 변수 선언
    3-2. 1은 제외, 2 ~ 주어지는 수까지 나머지가 0인 갯수를 변수에 저장
    3-3. 나머지가 0인 갯수가 1개이면 소수 갯수 변수에 +1
4. 소수 갯수 출력

 

참고 사이트

https://blognavercomcheetah254.tistory.com/43

[백준 1978번] 소수 찾기(파이썬)