본문 바로가기

수학8

[백준-실버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] 11653번 소인수분해 (수학, 파이썬) https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net - 입력 n이 1보다 큰 동안 while문을 통해 반복한다. - 그 안에서 for문을 2부터 n까지 돌면서 n % i ==0 (나누어 떨어지면) n = n//i로 업데이트하고 i를 출력하고 for문을 종료한다. n = int(input()) while n > 1: for i in range(2, n +1): if n % i ==0: n = n // i print(i) break 2022. 3. 4.

티스토리툴바