소수 판정16 백준 18384 자바 - PRIM (BOJ 18384 JAVA) 문제 : boj18384 이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다. 1. 1000000보다 처음으로 큰 소수까지의 모든 소수 2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기 '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다. '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 .. 2022. 3. 22. 백준 6219 자바 - 소수의 자격 (BOJ 6219 JAVA) 문제 : boj6219 1. 우선 A, B 사이의 소수를 어떻게 효율적으로 구할까? 에라토스테네스의 체 방식을 사용하여 미리 구해두면 된다. 이 때 내 경우엔 좀 더 효율적으로 하고자 sqrt(n)까지만 확인(왜 그래도 되는지는 여기를 확인해보면 된다.)하고, 짝수는 굳이 안봐도 되므로 아예 확인하지 않는 등의 약간의 추가 처리가 들어가있다. 코드에서 getPn()을 확인해보면 된다. 2. 다음으로 어떠한 정수가 있을 때 해당 수에 숫자 D가 포함되는지 어떻게 알 수 있을까? 가장 간단하게는 해당 정수를 String으로 변환하고 숫자 D도 character로 변경해서 확인해보는 방법이 있다. 당연히 좀 비효율적이다. 좀 더 빠르게 하려면 나머지 연산과 나누기 연산을 사용하면 된다. 어떠한 n에 대해 n%.. 2022. 2. 12. 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12. 백준 1017 자바 - 소수 쌍 (BOJ 1017 JAVA) 문제 : boj1017 애초에 해결을 위한 키 아이디어도 일반적으로 찾기 쉽지 않을듯하고, 거기에 네트워크 플로우에서 이분 그래프의 최대 유량을 구하는 이분매칭 알고리즘에다가 소수 판정(에라토스테네스의 체)에다가 값 압축(이건 필수는 아님)까지 들어간 플래3에 손색이 없는 문제였다. 구현이 다소 복잡했어서 틀리면 예외찾을 엄두가 안났었는데 다행히 운좋게 한방에 통과했다. 오랜만에 한방에 통과한게 찐텐으로 기뻤다ㅋㅋ 1. 일단 브루트포스로 모든 경우를 살펴본다면 50C2번에 걸쳐 더해서 소수쌍이 되는걸 구하고, 모든 소수가 되는 쌍에 대해 모든 N개가 서로 겹치지 않고 선택되는 경우를 살펴야 한다. 대강 모든 쌍의 합이 소수가 된다면 O((50C2)!) 정도가 될 것이므로 통과할 수 없다. 서로 최대한 쌍.. 2022. 1. 4. 백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA) 문제 : boj6588 1. 홀수인 소수란 말은 그냥 2를 제외한 소수라는 의미이다. 2 말곤 전부 홀수인 소수이다. 아무튼 그러니 100만 이하의 소수를 모두 구해준다. 에라토스테네스의 체를 사용해 입력받기전에 미리 구해두면 각 케이스에 대해 해당 소수들을 써먹을 수 있으니 효율적이다. 그리고 여러 방법이 있겠으나, 시간복잡도를 좀 손해보더라도 편하게 코드를 짜기 위해 TreeSet에 찾은 소수를 넣어두었다. 시간 복잡도에 중점을 두려면 소수를 hashSet에 넣고, 추가로 소수 순서대로 배열에 넣어두면 된다. 어차피 시간이 널널한 문제라 뭘 쓰던 상관없다. TreeSet은 set이므로 a+b = n을 찾을 때 a가 정해지면 b가 존재하는지 contains(n-a)로 확인할 수 있다. 또한 hashSe.. 2022. 1. 1. 백준 1747 자바 - 소수&팰린드롬 (BOJ 1747 JAVA) 문제 : https://www.acmicpc.net/problem/1747 풀이1 다소 어려워보일 수 있으나, 문제에서 원하는 부분을 순서대로 구현하면 어렵지 않다. 1. 소수를 알 수 있어야 한다. 이때, N은 최대 100만인데 문제에서 요구하는 것은 N 보다 '큰거나 같은 수'중 소수이면서 팰린드롬인 수 이므로 100만까지만 소수를 구해서는 안된다. 약간 범위를 늘려봐서 확인해보면 되는데, 결론적으로 1,003,001 까지 확인해보면 모든 입력에 대해 만족할 수 있다. 소수를 구하는 것은 에라토스테네스의 체를 사용하면 된다. 2. 소수 중 팰린드롬인 수를 알 수 있어야 한다. 숫자 자체로 맨앞과 맨뒤 문자열을 비교하며 중간까지 와도 되는데, 중간에서 멈추기가 좀 어렵다. 어차피 최대 100만 근처의 .. 2021. 11. 23. 이전 1 2 다음
