그건 장난감이 아니라 돌이야

컴퓨터 공학에 입문한 뒤 대부분 처음으로 배우는 소수 판별 알고리즘은 에라토스테네스의 체 알고리즘이다. 에라토스테네스의 체는 소수를 판별하고 싶은 범위 안의 소수인 수의 모든 배수를 차례로 제거해서 원하는 수의 범위에서 어떤 수가 소수인지 판별 할 수 있는 알고리즘이다. 이는 꽤나 직관적인 알고리즘으로, 알고리즘이 작동하는 방식을 보면 소수라는 체로 소수가 아닌 수를 거르는 것처럼 보인다. 따라서 알고리즘의 고안자인 에라토스테네스의 이름과 체를 붙여서 에라토스테네스의 체 라는 이름을 가지고 있다. 에라토스테네스의 체는 O(N^2) 시간복잡도를 가진 알고리즘이다. 그런데 놀랍게도 에라토스테네스의 체를 가르쳐 준 후, 컴퓨터 공학 학부를 졸업할 때까지 일반적인 학부 과정상에서 소수 판별에 대한 더 효율적인 ..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수이면서 펠린드롬인 수를 찾는 문제이다. 에라토스테네스의 체 알고리즘을 사용하면 쉬운 문제다. 에라토스테네스의 체란 소수를 판별하는 일종의 브루트포스 알고리즘이다. 꼭 체에 수를 걸러서 소수만 남기는 것 같다는 이유와 그리스의 수학자 에라토스테네스의 이름을 따서 에라토스테네스의 체라고 불린다. 더 자세한 설명은 여기로! 에라토스테네스의 체 팰린드롬이란 한글로 회문 즉 앞..