[백준] 1978번 : 소수 찾기 (Python)

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

 

 

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

 

import sys

input = sys.stdin.readline

def prime(N):
    
    for i in range(2, int(N ** 1/2)+1):
        
        if((N % i) == 0):
            return False
    
    return True

T = int(input()) # 테스트 케이스의 개수
case = map(int, input().split()) # 소수인지 판별할 값
num = 0

for i in case:
    
    if(i <= 1): # 1 이하는 소수 x
        continue
    
    if(prime(i)): # 소수면
        num += 1
    
print(num)

 

 

[문제풀이]

---

 

소수란 1과 자기 자신 외에는 나누어 떨어지지 않는 수를 의미한다.

반복문을 돌려 자기 자신 외에 나누어 떨어진다?

그럼 소수가 아니다!

int(N ** 1/2)+1

 

왜 N까지가 아니라 이렇게 했냐면 중간값을 넘으면 어차피 나누어 떨어지지 않는다.

그러니 확인할 필요도 없음!

 

예) 16 = 1 2 4 8 16

 

9 이상은 확인할 필요 x