[파이썬] 백준 1978번 소수 찾기 문제 풀이

문제 설명

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

 

문제 링크

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

입출력 예시

프로그램 코드

 

def is_prime(a):    #소수 구하는 함수
    if a == 1:      #숫자가 1이면 0 반환
        return 0
    for i in range(2, int(a ** 0.5) + 1):   # 2부터 숫자 제곱근까지 반복
        if a % i == 0:  #나눠지면 소수가 아니므로 0 반환
            return 0
    return 1

N = int(input())    #N 입력

cnt = 0 #소수 개수 저장할 변수
nums = input().split()  #숫자들 입력받는 변수

for i in nums:  #각 숫자마다 소수인지 검사
    if is_prime(int(i)):    #소수면 cnt 1증가
        cnt += 1

print(cnt)

 

프로그램 코드 설명

소수는 1과 자기 자신으로만 나눠지는 숫자를 의미한다.다른 말로 하면 1과 자기 자신 이외에는 나눠지는 약수가 없어야 한다.이 소수를 찾기 위해서는 2부터 해당 숫자 전까지 나눠지는 숫자가 있는지 없는지 확인을 하면 된다.만약 나눠지는 숫자가 있다면 이 숫자는 소수가 아닐 것이다.하지만 코드에서는 나눠지는 숫자가 있는지 검사를 해당 숫자의 제곱근까지 검사를 한다.이 이유는 실행시간을 줄이기 위한 방법이고, 자세한 설명은 아래 글에 있으니 참고하시기 바랍니다.

 

소수에 대한 문제 중 실행시간을 줄이는 문제는 아래에서 참고해보세요.https://imcoding-official.tistory.com/129

[파이썬] 백준 1929번 소수 구하기 문제 풀이