[알고리즘/자바] 백준 2960번 - 에라토스테네스의 체

2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 주어진 N이 소수라면 2보다 크거나 같고 N보다 작은 수로 나눠 떨어지면 안된다. ( 주어진 N이 N>2를 만족하는 자연수 ) 예를들어 10을 소수인지 판단 하려면 2보다 크거나 같고 9보다 작은 수로 나눠보면된다 ( 10은 소수가 아니기 때문에 2와 5로 나눠떨어진다. ) 즉 자기보다 작은 수에 의해 나눠떨어지면 소수가 아니다. 이 원리를 이용하면 소수를 빠르게 구할 수 있다. 그 중 대표적인 알고리즘이 에라토스테네스의 체. 에라토스테네스의 체는 특정 범위내에 있는 모든 소수를 빠르게 찾기 위한 알고리즘 중 하나이다. 에라토스테네스의 체를 이용해 ..

2021.01.03