아주 큰 소수를 찾아라
컴퓨터를 이용하여 97이 소수인지 합성수인지를 알아내기 위해서 다음 그림과 같은 순서도를 이용할 수 있다. 그러나 아주 큰 자연수 N이 소수인지를 알아내기 위해 이와 같은 알고리즘을 이용하면 컴퓨터를 이용하더라도 많은 시간이 걸린다. 하지만, 컴퓨터에 소수 2, 3, 5, 7, 11, … 등의 목록을 저장해 두고 있다면, 다음과 같은 수학적 사실을 이용하여 계산 시간을 크게 단축시킬 수 있다. "자연수 N이 이하의 모든 소수로 나누어 떨어지지 않으면 N은 소수이다." 예를 들어, 이므로 9 이하의 소수 2, 3, 5, 7만 생각하면 된다. 즉, 97은 2, 3, 5, 7로 모두 나누어 떨어지지 않으므로 97은 소수이다. 이와 같은 방법으로 100 이하의 소수 2, 3, 5, …, 97만으로 10000 이..
2012. 11. 13.
