|
http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Board&no=8479 [복사]
마지막 4번째 버젼입니다.
"모든 정수는 대칭하는 두수의 곱으로 나타낼수 있다"의 특성을 이용해
연산시간을 획기적으로 줄였습니다 -_-;;
예를들어 18이란 정수는 1*18 2*9 3*6 6*3 9*2 18*1 로 나타낼수 있죠.
여기서는 두 정수의 곱으로만 나타냈지만 실제로는 실수로도 가능합니다.
3루트3 * 2루트3 로도 나타낼수 있죠.
이처럼 대칭되어지는 두수의 곱으로 나타낼수 있기때문에 실제로 소수인지 확인
하기위해서는 대칭되어지는 점[입력값의 루트값 즉 sqrt()함수를 이용한 결과값]
까지만 연산을 해주면 된다는 결론이 나옵니다.
그래서 두번째 방법에 하나의 변수를 더 추가하여[sqrt_number] sqrt값을 만들어
내고 for문의 범위를 이 변수의 값까지로 한정시켰습니다.
속도는....가히 눈부시군요 -_- 2번째 버젼에서 39초나 걸렸던 "1234567891" 란
정수의 소수확인시 1초도 안걸립니다.....
결론: 알고리즘이란게 재밌군요. 이제 다른 주제로 알고리즘 연구를 해봐야겠습니
다. |
Hit : 6611 Date : 2007/02/23 06:09
|
22006, 
9/1101 
아이프리드
