푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다.www.acmicpc.net ✏️ 문제 설명  ✏️ 문제 풀이오일러 피 함수 문제에서 xφ(x) = n을 만족해야 한다는 조건이 추가되었습니다.φ(x)의 값은 무조건 정수이기 때문에 x는 n의 약수여야 합니다. 사실 어찌보면 당연할 수도 있습니다.여기서 얻을 수 있는 힌트는, n의 약수에 대해서만 φ(x)을 구해서 xφ(x)=n인지만 확인하면 됩니다.정리를 해보자면 주어진 n에 대해서 n의 약수를 모두 구한 뒤, 각 약수들에 대한 xφ(x)을 n과 비교하기 총 ..

Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피) 소수 구하기(에라토스테네스의 체 원리) ● 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 ● 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 숫자의 배수들을 배열에서 모두 지우기 ● 처음으로 선택된 숫자들은 지우지 않고 반복문을 N의 제곱근까지만 돌림 ● 시간 복잡도는 O(Nlog(logN)) 백준 1929번 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ※ N의 범위가 1,000,..