수다닷컴

가입 후 덧글을 올려야 글을 올릴 수 있다고 해서 덧글을 어디에 올려야 하나 찾던 중...
소수 구하기에 대한 글들을 읽어봤습니다.
대부분은 1부터 n 까지, 혹은 n/2 까지의 수를 나누어서 판별하던데...(뭐 하나하나 다 살펴보진 않았습니다.)
얼마 전 책에서 소수 구하기 소스를 보니까 1부터 √n 까지의 정수만 나누어서 판별하더군요.
혹시 나중에 소수 구하는 코드를 짜려고 하는데 어려움이 있는 분들이 계실 때 참고할 자료를 하나 더 추가하는 의미에서...
이 글을 올립니다.

네이버 백과사전에도 소수에 대한 내용을 보면 다음 내용이 있습니다.
자연수 n이 소수인지 아닌지를 판정하려면, 2≤p≤ √n인 범위에 있는 모든 소수 p로 n을 나누어 보아,
나누어지지 않으면 소수이고, 나누어지면 합성수이다.

잘 이해가 안가더라구요. 왜? √n 까지만 나누어보면 되는가??
n/2 까지만 나누어 보면 된다는 거는 금방 이해가 가는데 말이죠.
어떤 수의 약수 중 최소는 2 이고 최대는 n/2이니까요.

연습장에 막 끄적거리면서 생각하던 중 옛생각(?)이 났습니다.
초등학교 때 속셈학원에서 배운 기억에는, 두 개씩 짝을 지어 약수를 구했습니다.
아마도 누구나 그렇게 배웠겠지요?
연습장에 가운데 줄을 그어 왼쪽 편 오른쪽 편 나눈 다음,
2부터 나누어가면서 나누어지면 왼쪽 편의 왼쪽부터 그 수를 쓰고 오른쪽 편의 오른쪽부터 나눈 값을 써나가지요...
만약 120 의 약수를 구한다 치면...
2| 60
2,3 | 40,60
2,3,4 | 30,40,60
2,3,4,5| 24,30,40,60
2,3,4,5,6| 20,24,30,40,60
2,3,4,5,6,8 | 15,20,24,30,40,60
2,3,4,5,6,8,10 | 12,15,20,24,30,40,60
이런 식으로 했습니다.

다시 생각해보면, n 의 약수들은 서로 곱해서 n 이 나오는 수들의 집합이란 얘긴데...
위와 같이 왼쪽 편에 있는 수, 오른쪽 편에 있는 수를 나누어본다면
왼쪽 편에 있는 수 중 가장 큰 수 a 는 오른쪽 편에 있는 수 중 가장 작은 수보다 작거나 같고...
또한 a 는 √n 보다 절대로 클 수가 없습니다.

√n에서 소수점을 버린 수가 a 라고 한다면...
n 은 a^2 과 (a+1)^2 사이의 수일 것입니다.
만약 n 의 약수를 구했더니 왼쪽 편에 있는 약수 중 a+1 이 있다고말한다면,
그 말은 오른쪽 편에 a+1 과 같거나 더 큰 수가 있어야 한다는 말인데,
그렇게 되면 그것을 약수로 갖는 수가 (a+1)^2 이상이라는 얘기고, 그렇다면 그건 n 보다 큰 수가 되니까...
결국 왼쪽 편에 있는 약수 중 a+1 이 있다는 말은 거짓이 됩니다.

말하자면...n 의 약수를 구할 때는 2 부터 √n 까지의 수만 나누어보면 됩니다.
그러면 나머지 약수는 자연히 구해지게 되는 것이구요.
그렇다면 소수인지 아닌지 판별할 때도 마찬가지로 하면 된다는 뜻이 되겠죠...
2 부터 √n 까지의 수를 나누어봐서 하나도 나누어지지 않는다면 그건 소수...아니면 합성수...

여기까지 그냥 저 혼자 멋대로 생각해본 것이구요...
혹시 그럴듯하게 제대로 수학적 증명을 하려면 어떻게 해야 하는지 아시는 분 계시면 답글 좀 달아주세요...PS :
양의 제곱근 구하는 메서드 - Math 클래스의 sqrt(double a) 메서드.
예) 246 의 제곱근에서 소수점 버린 정수a구하기 :
inta = (int)Math.sqrt(246);
System.out.println(a);
실행 결과 = 15

신청하기