[BOJ] - 기본 수학 2 - 소수 - (1) - Python

소수(Prime number)는  1과 자신의 숫자 이외에 나눠질 수 없는 숫자를 말합니다.

소수를 찾는 함수를 만드는 방법에는 두 가지가 있었습니다. (제가 풀었던 방법 내에서 말씀드립니다.)

 

 - 소수가 n이면 2부터 n-1까지 나눠서 한번이라도 나누어떨어지면 소수가 아님을 반환

 - 소수가 n이면 2부터 sqrt(n) 전까지 나눠서 한번이라도 나누어떨어지면 소수가 아님을 반환

 

첫번째 방법은 O(n) 시간만큼 걸리고 두번째 방법은 O(n^0.5) 시간만큼 걸린다고 합니다. 당연히 덜 나누는게 더 빠르겠죠?

두번째 방법은 에라토스테네스 체 알고리즘 내용입니다.

8의 경우 약수는 1, 2, 4, 8 이므로 sqrt(8) = 약 2.8로 1, 2 까지만 나눠도 됩니다. 4와 8은 이미 2에서 나눴으니까요. 이렇게 접근하시면 이해가 빠르실겁니다. (2*4 = 4*2 대칭)

아직 두번째 방법은 구글링하면 바로 나오지만, 제 생각의 코드로 구현해보진 못했습니다.

(다 풀고 소수 2편에서 기록 남기기로 하겠습니다.)

1978: 소수 찾기

# 1978: 소수 찾기
N = int(input())
numbers = list(map(int,input().split()))

def prime_num(n) :
    if n == 1 :
        return 0

    if n == 2 :
        return "prime number"

    sum = 0
    for i in range(2, n) :
        if n % i == 0 :
            sum += 1
        else :
            continue

    if sum >= 1 :
        return 0
    else :
        return "prime number"

prime = []
for j in range(len(numbers)) :
    if prime_num(numbers[j]) == "prime number" :
        prime.append(numbers[j])

print(len(prime))

2581: 소수

# 2581: 소수
M = int(input())
N = int(input())
numbers = list(range(M, N+1))

def prime_num(n) :
    if n == 1 :
        return 0

    if n == 2 :
        return "prime number"

    sum = 0
    for i in range(2, n) :
        if n % i == 0 :
            sum += 1
        else :
            continue

    if sum >= 1 :
        return 0
    else :
        return "prime number"

prime = []
for j in range(len(numbers)) :
    if prime_num(numbers[j]) == "prime number" :
        prime.append(numbers[j])

if len(prime) == 0 :
    print(-1)
else :
    print(sum(prime))
    print(min(prime))

확실히 prime number로 문자열을 return 하는것보다 True False의 bool로 reutrn하는게 좋겠네요.