본문 바로가기
728x90

전체 글423

[python] 백준 1850 최대공약수 import sys input = sys.stdin.readline a, b= map(int, input().split()) def gcd(a,b): if b==0: return a return gcd(b, a%b) ans = gcd(a,b) while ans: print(1, end='') ans -= 1 2023. 2. 24.
[python] 백준 11689 GCD(n, k) = 1 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 n의 약수 중 소수인 것을 $p_{1}, p_{2}, ... p_{a}$ 라 할 때 소수의 개수는 다음과 같이 구할 수 있다. $\phi$ (n) = n $\times \prod_{i=1}^{a} (1-\frac{1}{p_{i}})$ 시간초과가 나지 않게 리스트를 사용하지 않고 for문을 돌면서 소수를 찾으면 ans -= ans/p 를 한 다음 n에서 소수 p의 흔적을 없앤다. p를 약수로 갖지 않을 때 까지 계속 나눠준다는 것이다... 2023. 2. 24.
[python] 백준 1747 소수&팰린드롬 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 해결 n이상의 소수에서 찾는 것이므로 리스트의 원소 개수를 1,000,000(n의 최댓값)보다 커야한다. ($\times$ 10 함) 소수는 에라토스테네스체로 걸러낸다. CODE import sys input = sys.stdin.readline import math n = int(input()) A = [0]*(10000001) for i in rang.. 2023. 2. 23.
[python] 백준 1456 거의 소수 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 해결 편하게 0부터 끝 수(b)까지 리스트 만들어 놓고 하면 메모리 초과가 걸린다. 따라서 int(sqrt(b))+1 개의 리스트 공간을 만들어 놓고 소수인 인덱스를 제곱, 세제곱 하면서 a와 b 사이에 들어오는지를 확인해야 할 것이다. CODE import math import sys input = sys.stdin.readline a, b = map(int, input().split()) A = [.. 2023. 2. 23.
728x90