본문 바로가기

파이썬/알고리즘

(42)
백준 9020번 [Python] 문제풀이(골드바흐의 추측) - 이정개 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수..
백준 1929번 [Python] 문제풀이(소수 구하기) - 이정개 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 3 16 예제 출력 1 3 5 7 11 13 알고리즘 분류 ㆍ에라토스테네스의 체 파이썬 코드(시간초과) m, n = map(int, input().split()) def isPrime(x): # 소수를 판별하는 함수 if(x 1 and prime[i] == True: # 1 이상이면서 남은 소수들을 출력 print(i) isprime(m, n) 시간을 줄이는 방법은 여러가지가 있지만 문제에 제시되어있는 에라토스테네스의 체를 활용하기로 하였다. 에라토스테네스의 ..