[백준/파이썬] 1978 소수 찾기 알고리즘 구현하기

백준 1978 소수 찾기를 풀었습니다.

 

소수 찾기 알고리즘을 모른다면 좀 막막할 수도 있습니다.

중학교 때 배웠던 에라토스테네스의 체가 생각나기도 하고,

모든 수를 다 나눠줘야 하나 막막하기도 합니다.

 

막막하다면 아래 코드를 참고하시는 것도 좋을 것 같습니다.

primeNumber()라는 함수로 구현해두었는데,

백지 상태에서 구현하기에는 쉽지 않은 코드입니다.

 

이런 식으로 하면 되는구나를 익히고 외우는 게 더 좋은 공부이지 않을까 싶습니다!

 

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

1978번: 소수 찾기

728x90

import sys

def primeNumber(x):
    if x == 1:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

n = int(sys.stdin.readline())
numList = list(map(int, sys.stdin.readline().split()))

count = 0
for num in numList:
    if primeNumber(num) == True :
        count += 1

print(count)

반응형

 

풀이 아이디어

1. 소수 찾기 함수 : 알아보고자 하는 수(x)가 소수일 때 True를, 소수가 아닐 때 False를 반환하는 함수입니다. x가 1이면 소수가 아니기 때문에 False를 반환합니다. 2부터 x-1까지 x와의 나머지 연산에서 0이 되는 경우를 찾습니다. 1과 자기 자신은 소수가 아니기 때문에, 2부터 x-1까지 루프를 돌리는 것입니다.

2. numList 라는 리스트를 만들고, 공백을 기준으로 요소값을 입력합니다. 그 요소가 소수라면(True)라면 개수를 하나 세줍니다.(count += 1)

 

 

*주의사항*

1. 수가 1일 때를 체크해야 합니다.

2. 소수 찾기 함수에서 반복문 범위를 주의해야 합니다.

SMALL