소수 판별하기
2018. 8. 24. 12:59
백준 1978번을 풀다가 소수에 대해 생각했다. 문제의 핵심은 1000이하의 N개의 숫자가 주어졌을 때 소수의 개수를 새는 것이다. 처음에는 소수의 특징을 파악한 후 각 숫자가 소수인지 아닌지를 판별하는 방법을 써야하나 싶었는데,소수가 1과 본인을 제외한 수로 나눠지지 않는다는 특징 때문에 위의 방법을 사용하기 어려웠다. 결국 가장 효율적이라고 알려진 '에라토스테네스의 체'라는 방법을 이용해 1000이하의 수 중에서 소수만 리스트에 남기고입력받은 수 중에 리스트에 포함되있는 수를 세어 결과를 산출했다. 소수를 세기 위한 방법으로는 숫자를 그 이하 모든 수로 나눠 떨어지는지 확인하는 방법을 가장 쉽게 생각할 수 있다.이를 더 효율적으로 하기 위해 소수가 아닌 수는 결국 곱으로 나타낼 수 있고 n의 제곱근을..