에라토스테네스의 체. 이름이 조금 어려운 알고리즘입니다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수(Prime Number)를 찾는 알고리즘 중 하나인데요. 일반적으로 정수 n이 소수인지 확인할 때, for문을 돌리며 2~sqrt(n)으로 나누어 떨어지나 확인하는 방법이 있습니다. 하지만 특정 범위 내 여러 개의 수를 소수인지 판단해야 할 때, 각각 2~sqrt(n)으로 나누어 떨어지는지 확인하는 것은 조금 비효율적일 수 있습니다. 하지만, 처음에 범위 내 숫자들에 대해 소수인지 구해놓고 이후에 각 숫자들이 소수인지 확인한다면 더 빠르게 작동할 수 있습니다. 에라토스테네스의 체 에라토스테네스의 체의 원리를 그림으로 표현하자면 위 이미지와 같습니다. 2 ~ 120 범위 내 숫자들..

https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 난이도 : 플래티넘 3 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체, 이분 매칭 설명 소수 판정 + 이분 매칭 문제입니다. 이분 매칭에 관해서는 아래 글을 참고해주세요. https://uknowblog.tistory.com/444 [알고리즘] 이분 매칭 (Bipartite Matching) 이분 매칭을 간단히 이야기하면 연애 매칭 프로..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체 설명 한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다. 목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다. 너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다. https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 정수론, 소수판정, 에라토스테네스의채 설명 상당히 어려웠던 문제였습니다 그냥 단순히 입력으로 주어지는 연산을 그대로 했더니 당연하게 시간초과 발생하였고, *, / 연산을 각각 리스트로 만들어 6 -> 2 * 3, 10 -> 2 * 5와 같이 소인수 분해 한 후, 각각에 리스트에 넣어준 뒤 (첫 항은 *로 처리), * 연산이 남아있으면 유리수, / 연산이 남아있으면 유리수로 판단하였습니다. 6 / 4 = (3 * 2) / (2 * ..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체 설명 골드바흐 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측입니다. 아직 수학적으로 증명되지 않았기에 추측이라고 불립니다. 4보다 큰 짝수를 두 홀수 소수의 합으로 나타낼 수 있을 경우, 두 소수의 차이가 가장 큰 두 수를 출력, 나타낼 수 없을 경우 "Goldb..

https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 브루트포스 알고리즘, 정수론, 소수 판정, 에라토스테네스의 체 설명 소수이면서, 동시에 팰린드롬인 수를 찾는 문제입니다. 팰린드롬은 그냥 단순히, 문자열을 뒤집었을 때 같은 문자열 (ex> 토마토, 기러기)을 팰린드롬이라고 합니다. 해당 문제에서는 에라토스테네스의 채가 유용하게 쓰일 것 같네요. 에라토스테네스의 채? http..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 난이도 : 골드 5 태그 : 수학, 정수론, 백트래킹, 소수 판정 설명 백트래킹 + 소수판정 문제입니다. 백트래킹으로 수열을 구한 뒤, 수열을 숫자로 바꿔 해당 숫자가 소수인지 판단하였습니다. 소스코드 시간초과 var n = -1 lateinit var nums: Array val sb = StringBuilder() fun main() { n = readln().toInt() nums..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 난이도 : 실버 5 태그 : 정수론, 수학, 소수판정 설명 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주어진 n개의 수 중 소수를 찾는 문제입니다. 소수를 판단하는 방법은, 2부터 해당 수 - 1까지 나눠진다면 소수입니다. 소스코드 re = int(input()) nu..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 정수론, 소수 판정 설명 N에 대해 소인수분해를 하는 문제입니다. 소인수분해 과정은 꽤 간단합니다. 60을 소인수분해 한다 했을때, 60 / 2 = 30 이며, 30 / 2 = 15 입니다. 2로는 더 이상 나눠지지 않으니 3으로 나눠봅시다. 15 / 3 = 5 이며, 더 이상 3으로 나누어지지 않고, 4로도 나누어지지 않습니다. 5 / 5 = 1 입니다. 이와 같이 60을 소인수분해 하면 2 * 2 * 3 * 5 = 60을 구할 수 있습니다. 소스코드 fun main() { v..