에라토스테네스의 체 "에라토스테네스의 체(Sieve of Eratosthenes)"는 3세기의 그리스 수학자 에라토스테네스가 정리한 소수를 찾는 방법이다. n이하의 자연수에서 소수의 배수를 차례대로 소거하여 최종적으로 n이 남아있다면 n은 소수임을 알아낼 수 있다. 에라토스테네스의 체 구현에는 해당 수가 소수인지 아닌지만 저장하는 bool형의 자료구조가 필요하며, 아래 두 가지의 최적화를 거친다. 1. n이 인수가 있다면 인수는 √n 이하의 수와 그 이상의 수의 쌍으로 이루어지기 때문에 √n의 수까지만 확인해도 판정이 가능하다. 2. i의 배수를 지울때는 i*i이하의 값들은 이미 i이하의 값의 배수(ex. i*3, i*4, i*5 ... i*(i-1) 는 이미 소거)이므로 i*i이상의 값부터 소거하면 된..

문제 https://algospot.com/judge/problem/read/PASS486 algospot.com :: PASS486 비밀번호 486 문제 정보 문제 재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 "no-smok**X**" 와 같이 정하는데, 여기서 X algospot.com 풀이 종만북 난이도: 중 에라토스테네스의 체를 활용한 소인수 분해를 이용해야해서 어려웠던 문제이다. 특히 소인수 분해까지는 구현해도 수학적인 최적화를 진행하지 않으면 제 한 시간 안에 맞출 수 없다. 해당 문제에서 사용되는 에라토스테네스의 체와 소인수 분해는 아래 링크에서 확인하자. 에라토스테네스의 체와 소인수 분해 어떤 수n의 약수의 개수를 ..