lastknight00

문제 링크 : [백준]소수마을(14431) 문제 설명 소수마을과 A마을, N개의 마을들의 좌표가 주어집니다. 소수마을에서 A마을까지 이동하려고 하는데, 이동 할 때는, 이동거리가 소수인 경우에만 이동 할 수 있습니다. 이동거리는 두 마을간의 이동 거리이며, 소수점은 버립니다. 소수마을에서 A마을까지의 최단거리를 구하세요. 입력 Px Py Ax Ay(소수마을의 좌표, 마을의 좌표) N(마을의 갯수, 1

문제 링크 : [백준] 소수상근수(9421) 문제 설명 상근수 : 각 자리의 수를 제곱하여 더한 값이 1이면, 상근수, 아닌 경우, 앞의 행위를 계속 반복(1이 아닌 값에서 싸이클이 발생할 경우 상근수 아님) 소수상근수 : 상근수중 소수인 수 n이 주어질 때, n보다 작거나 같은 수 중, 모든 소수상근수를 출력하세요. 입력 N(1

문제 링크 : [백준] 소수 사이 수열(3896) 문제 설명 n이 주어지면, n보다 작거나 같은 소수 중 가장 큰 수와 n보다 크거나 같은 소수 중 가장 작은 소수의 차이를 구하세요. 입력 T(테스트 케이스 수) Ni(n, 1 < Ni < 1,299,709) 5 10 11 27 2 492170 출력 4 0 6 0 114 카테고리 #에라토스테네스의 체 #이분탐색 시간 복잡도 상한 O(NlogN) 해결 방법 에라토스테네스의 체로 N의 최대값보다 하나 더 큰 소수까지를 구합니다. lower_bound로 N보다 크거나 같은 소수 중 가장 작은 소수(그 위치를 p라고 함)를 구합니다. 그 수가 소수라면, 0을 출력합니다. 그 수가 소수가 아니라면, p번째 소수와 p-1번째 소수의 차이를 출력합니다. 이렇게도 풀..