프로그램을 작성할 때 소수를 구해야 할 일이 종종 있다. 이 때에는 조건에 따라 두 가지 방법 중 적절한 것을 골라서 사용하게 된다.
2 ~ √N 중 약수 검사하기
이 방법은 N이 소수인지 아닌지를 판별하는 방법으로, 매우 직관적이다. 일반적으로 √N까지의 수 중에 N의 약수가 없으면 그 이후의 수에도 N의 약수가 없다는 것을 가지고 N의 소수 여부를 검사하는 방법이다.
위 프로그램은 입력한 수가 소수인지 아닌지를 알려준다. 2부터 √N까지의 수 중에 N의 약수가 있는지를 검사하는 방법이다.
위 방법은 특정 수의 소수 여부를 판별하기에는 빠르다는 장점을 가지고 있다. 하지만 일정 범위의 모든 수 중 소수를 구할 때 쓰기에는 아래의 방법보다 훨씬 비효율적일 수 있다.
에라토스테네스의 체
이 방법은 에라토스테네스가 고안한 방법으로, 여러 수를 체를 이용해 거르는 모양과 흡사하다고 해서 아리스토테네스의 체라고 불리운다.
2부터 N까지의 수 중 소수를 구한다고 하자. 이 때 K가 소수일 때 K의 배수는 소수가 될 수 없다. 가장 작은 소수는 2이며, 따라서 2의 배수는 소수가 될 수 없다. 이 때 모든 2의 배수에 체크를 시켜둔다. 체크되지 않은 수 중 가장 작은 수는 3이고, 3의 배수에도 모두 체크한다. 이러한 방법으로 N까지 검사하면 2~N 사이에 있는 모든 소수를 빠른 시간 내에 구할 수 있다.
아리스토테네스의 체를 C로 작성해보면 위의 소스와 같다. 2의 배수는 모두 소수가 아니라는 점에 착안하여 메모리 사용과 실행 속도를 반으로 줄이는 방법도 있으나 편의상 그러한 방법은 사용하지 않았다.
위의 방법을 쓰면 상당히 빠르게 소수를 구할 수 있다. 특히 수가 커지면 커질 수록 처음의 방법보다 더 빠른 결과를 보여준다. 다만, 메모리가 많이 쓰이고 임의의 수의 소수 여부를 판단하는 데에는 적절치 못하다.
출력 부분을 제외하고 2부터 N까지의 모든 소수를 구할 때의 수행 속도는 다음과 같다.
수행 속도의 단위로 쓰인 tick은 ms와 거의 같은 단위로 봐도 무방하다. (따지자면 차이가 있지만 같다고 간주하자.) 대부분의 프로그램 문제에서는 1초 내에 처리할 것을 요구하므로 1,000,000 정도까지의 소수를 구하는 데에는 무리가 없을 것이다.
다만 주의할 점은 특정 범위(N~M)의 소수를 구하고 싶어도 2부터 M까지 돌려야 한다는 것이다.
문제의 요구에 따라 두 방법 가운데 적절한 방법을 골라 쓸 수 있어야 할 것이다.
2 ~ √N 중 약수 검사하기
이 방법은 N이 소수인지 아닌지를 판별하는 방법으로, 매우 직관적이다. 일반적으로 √N까지의 수 중에 N의 약수가 없으면 그 이후의 수에도 N의 약수가 없다는 것을 가지고 N의 소수 여부를 검사하는 방법이다.
위 프로그램은 입력한 수가 소수인지 아닌지를 알려준다. 2부터 √N까지의 수 중에 N의 약수가 있는지를 검사하는 방법이다.
위 방법은 특정 수의 소수 여부를 판별하기에는 빠르다는 장점을 가지고 있다. 하지만 일정 범위의 모든 수 중 소수를 구할 때 쓰기에는 아래의 방법보다 훨씬 비효율적일 수 있다.
에라토스테네스의 체
이 방법은 에라토스테네스가 고안한 방법으로, 여러 수를 체를 이용해 거르는 모양과 흡사하다고 해서 아리스토테네스의 체라고 불리운다.
2부터 N까지의 수 중 소수를 구한다고 하자. 이 때 K가 소수일 때 K의 배수는 소수가 될 수 없다. 가장 작은 소수는 2이며, 따라서 2의 배수는 소수가 될 수 없다. 이 때 모든 2의 배수에 체크를 시켜둔다. 체크되지 않은 수 중 가장 작은 수는 3이고, 3의 배수에도 모두 체크한다. 이러한 방법으로 N까지 검사하면 2~N 사이에 있는 모든 소수를 빠른 시간 내에 구할 수 있다.
아리스토테네스의 체를 C로 작성해보면 위의 소스와 같다. 2의 배수는 모두 소수가 아니라는 점에 착안하여 메모리 사용과 실행 속도를 반으로 줄이는 방법도 있으나 편의상 그러한 방법은 사용하지 않았다.
위의 방법을 쓰면 상당히 빠르게 소수를 구할 수 있다. 특히 수가 커지면 커질 수록 처음의 방법보다 더 빠른 결과를 보여준다. 다만, 메모리가 많이 쓰이고 임의의 수의 소수 여부를 판단하는 데에는 적절치 못하다.
출력 부분을 제외하고 2부터 N까지의 모든 소수를 구할 때의 수행 속도는 다음과 같다.
| N | 수행 속도(tick) |
| 10,000 | 0 |
| 100,000 | 15 |
| 1,000,000 | 282 |
| 10,000,000 | 3265 |
| 100,000,000 | 33813 |
수행 속도의 단위로 쓰인 tick은 ms와 거의 같은 단위로 봐도 무방하다. (따지자면 차이가 있지만 같다고 간주하자.) 대부분의 프로그램 문제에서는 1초 내에 처리할 것을 요구하므로 1,000,000 정도까지의 소수를 구하는 데에는 무리가 없을 것이다.
다만 주의할 점은 특정 범위(N~M)의 소수를 구하고 싶어도 2부터 M까지 돌려야 한다는 것이다.
문제의 요구에 따라 두 방법 가운데 적절한 방법을 골라 쓸 수 있어야 할 것이다.
2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
댓글을 달아 주세요
ㅋㅋ √N 쓸때면 거기에 +1을 해서 검사해야 하는것 아닌가 하고 조금 불안해지죠 ㅋ
저도 계속 헛갈립니다.. 혹시 소스에 문제 있는지좀 봐주세요. 막 작성한 거라 어떨지 모르겠네요.
특별히 문제는 없어보여요...^^
그리고 제곱수의 제곱근이 제대로 정수로 나오기만 한다면 √N까지만 해도 상관없어요..