[파이썬] 백준 9020 : 골드바흐의 추측

[파이썬] 백준 9020 : 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 실버 1 정수론, 소수 판정 접근 먼저 아리토스테네스의 체를 이용해 소수를 판정한다. 제곱근보다 작은 수 범위에서 합성수를 걸러내면 빠르게 소수를구할 수 있다. 소수중에서 x2를 한 값이 입력한 값을 넘는 경우부터 구한 소수를 역순으로 탐색하면서 두 소수의 합이 입력한 값과 같은 경우일 때를 출력하도록 했다. 다만 이 방법은 입력한 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 1.
• textsms

[파이썬] 백준 4948 : 베르트랑 공준

[파이썬] 백준 4948 : 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 실버 2 정수론, 소수 판별 접근 에라토스테네스의 체로 소수를 판별하는 방법을 사용하면 간단하게 구할 수 있다. 다만 내가 작성한 방법은 pypy3에서만 통과되었다. 코드 import sys; input = sys.stdin.readline def isPrime(num): for i in range(2, int(num**0.5) + 1): if n..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms