관리 메뉴

솜씨좋은장씨

[BaekJoon] 2581번 : 소수 (Python) 본문

Programming/코딩 1일 1문제

[BaekJoon] 2581번 : 소수 (Python)

솜씨좋은장씨 2021. 4. 27. 00:23
728x90
반응형

코딩 1일 1문제! 오늘의 문제는 백준의 소수입니다.

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

Solution

def get_primary_num_eratos(N):
    nums = [True] * (N)
    
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]

def solution(A, B):
    primary_nums = [num for num in get_primary_num_eratos(B + 1) if A <= num <= B]

    if len(primary_nums) == 0:
        print("-1")
    else:
        print(sum(primary_nums))
        print(min(primary_nums))
    
if __name__ == "__main__":
    inputNum1 = int(input())
    inputNum2 = int(input())
    
    solution(inputNum1, inputNum2)

Solution 풀이

소수를 찾는 방법에는 에라토스테네스의 체 방법을 활용했습니다.

입력 받은 두 수 중에 큰 수를 기준으로 소수를 모두 찾고

두 수 사이에 있는 소수만 추렸을 때 

소수가 하나도 없었다면 -1을 프린트하고

그렇지 않다면 소수들의 합과 가장 작은 소수를 두줄에 걸쳐 출력합니다.

 

SOMJANG/CODINGTEST_PRACTICE

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

Comments