본문 바로가기

에라토스테네스의채4

[백준-실버1] 9020번 골드바흐의 추측 (수학, 파이썬) https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net - 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. - 우선 에라토스테네스의 채로 소수를 체크한다. - n을 입력받고, for문을 도는데 이때 시작을 n//2부터 2까지 역순으로 순회한다. -> 이때 check[n-i] and check[i] 즉, n을 두 소수의 합을 나타낼 수 있을 때 -> n이 8이면 (4, 4), (5, 3), (6,.. 2022. 3. 4.
[백준-실버2] 4948번 베르트랑 공준 (수학, 파이썬) https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net - 에라토스테네스의 채를 이용해서 Max(123456*2)만큼 소수를 찾는다. - 입력을 받고, for문을 통해 n초과 2*n이하 만큼 돌면서 check == True이면 cnt를 1 증가시킨다. import sys input = sys.stdin.readline Max = 123456 * 2 check = [True]* (Max + 1) check[0] = check[1] = False .. 2022. 3. 4.
[백준-골드5] 17425번 약수의 합 (수학, PyPy3) https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - dp 리스트에 각 수에 해당하는 약수의 합을 계산해서 넣는다. -> 에라토스테네스의 채 같은 느낌 -> 모든 수는 1을 약수로 가지기 때문에 dp 리스트는 1로 초기화한다. - s 리스트는 약수의 누적합을 담는 리스트이다. -> for문을 돌면서 s리스트의 인덱스 -1 + dp리스트를 해서 누적합을 계산한다. import sys input.. 2022. 3. 4.
[백준-실버5] 2581번 소수 (수학, 파이썬) https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net - 소수를 판별하는 문제이다. - 소수를 코드로 구현할때는 2가지 방법이 있다. ( is_prime 함수 구현, 에라토스테네스의 채) - 에라토스테네스의채는 1 ~ N 범위 안에 있는 모든 소수를 구하는 방법이다. (시간 효율이 좋음) -> 구현 방법은 가장 작은수부터 배수를 지워나가는 방법이다. -> 0, 1은 소수가 아니므로 False처리를 미리 해준다. -> 2부터 2를 제외한 2의 배수를 다 Fals.. 2022. 3. 4.

티스토리툴바