22009,

1/1101

아이프리드

http://eloiz.woobi.co.kr/JavaPlus/

primeNumber_4.java (1.8 KB), Download : 92 [오른쪽 버튼 눌러 다운 받기]

[re] [re] 소수인지 확인하는 알고리즘.

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 : 6636 Date : 2007/02/23 06:09