기록방

👉 문제링크 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 1부터 자연수 n까지의 범위에서, 최대공약수(GCD)가 1인 자연수의 개수를 구하는 문제이다. 다시 말하면 서로소의 개수를 구하는 문제이다. 🔸 문제 풀이 🔸 서로소 개수를 구하는 공식으로 오일러의 피 함수(Euler product formula; 오일러 곱 공식)을 사용한다. n의 소인수로 P[i] = P[i] - P[i]/K (i는 K의 배수) 연산을 반복한다. n이 소수이거나, n이 지수가 1인 소인수를 가지는 경우, 오일러 피 함수를 1회 더 적용한다. 🔸 코드 🔸 impo..

👉 문제링크 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 🔸 문제 분석 🔸 주어진 범위에서 1보다 큰 수의 제곱수로 나누어 떨어지지 않는 수의 개수를 출력한다. 최소값이 1부터 1조, 최대값은 최소값부터 100만을 더한 값까지 주어진다. 🔸 문제 풀이 🔸 min과 max의 값이 1조까지 크게 주어지므로 long으로 받야아 한다. 제곱수를 확인하기 위해 에라토스테네스의 체 알고리즘을 사용한다. 배열의 크기를 max-min+1 만큼 차이로 선언한다. 제곱수의 배수를 max까지 계산하며 에라토스..

👉 문제링크 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 🔸 문제 분석 🔸 소수를 구한 후 오름차순으로 팰린드롬을 찾아 출력한다. 🔸 문제 풀이 🔸 N이 100만까지 입력되는데, 여유있게 1000만까지 소수를 구한다. 팰린드롬은 수를 char배열로 변환한 뒤 투포인터로 판단한다. 🔸 코드 🔸 import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

👉 문제링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 소수의 N제곱 (N>2)의 수를 거의 소수라고 한다. A이상 B이하의 거의 소수의 개수를 출력한다. (1

👉 문제링크 1418번: K-세준수 첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 자연수의 소인수중 최대값이 K보다 크지 않으면 K-세준수이다. N이하의 자연수 중에 K-세준수의 개수를 구한다. 🔸 문제 풀이 🔸 1부터 N까지의 자연수들 각각 최대 소인수를 구하고, 그 값이 K를 넘는지 확인해야 한다. 소인수 인지 확인하기 위해 자연수를 N까지 키워간다. 현재 수가 소인수이면 그 수의 N보다 작은 배수들은 현재 수를 소인수 최대값으로 저장한다.(에라토스테네스의 체) 만약 현재 수가 이전에 배수로 소인수를 구했으면 그 수와 K를 비교하고, 이전에 구한 값이 없으면 현재 ..