https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 설명 소수 A를 소수 B로 바꾸는 최소 단계를 구해야 한다. A를 B로 바꿀 때는 한 자릿수만 바꿀 수 있으며 바꾼 수 또한 소수여야 한다. 또한 네 자리 소수만 허용하므로 0039와 같은 수는 안 된다. 풀이 방법 이 문제는 소수 구하기와 BFS가 결합된 문제이다. 소수 구하기 에라토스테네스의 체를 활용해서 해결한다. import java.io.*; import java.util.*; class M..

https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 설명 N이 주어졌을 때 N보다 크거나 같고, 소수이면서 팰린드롬인 가장 작은 수를 출력하면 된다. 풀이 방법 이 문제는 소수 구하기와 팰린드롬 판별하기가 결합된 문제이다. 소수 구하기 에라토스테네스의 체로 구한다. 팰린드롬 판별 팰린드롬을 간단하게 판별하는 방법이 있다. 숫자를 문자열로 바꾼다. 문자열을 절반으로 나누어 각각 다른 변수에 저장한다. 뒤쪽 ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 설명 소수 구하기와 투 포인터가 결합된 문제였다. N이 주어지면 해당 N까지의 소수를 모두 구한 뒤 투 포인터를 활용해 합이 되는 연속된 합의 개수를 카운트하면 된다. 풀이 방법 소수를 구하는 방법으로는 에라토스테네스의 체를 활용한다. 이때 소수는 ArrayList에 담는다. 주의할 점은 대부분의 소수 탐색의 경우 N의 제곱근까지 수행하지만 이 문제의 경우 N까지의 소수들에 대한 연속합을 구하기 위해 ArrayList에 소수를 담아야 하므로 N까지 모든 수들을 탐색한다. for 문을 한 번 더 사용해서 첫 번째..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 설명 골드바흐의 추측은 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들어 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수 n이 주어졌을 때..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 설명 7331과 같이 7331도 소수, 733도 소수, 73도 소수, 7도 소수인 수를 신기한 소수라고 한다. 자릿수가 주어졌을 때 해당 자릿수의 신기한 소수를 모두 찾아내 오름차순으로 출력하는 프로그램을 작성하면 된다. 자릿수 N은 1 이상, 8 이하이다. 풀이 방법 1. 나의 풀이 - 통과 코드로 보는 편이 빨라 코드와 주석으로 설명하겠다. import java.io.*; cl..