22010,

1/1101

아이프리드

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

primeNumber_second.java (1.6 KB), Download : 24 [오른쪽 버튼 눌러 다운 받기]

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

http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Board&no=8472 [복사]

===============================================================================

>
> 간단히 만들어봤는데...
>
> 문제는 숫자가 커질수록 기하급수적으로 늘어나는 계산시간이란겁니다 -_-;;
>
> for문을 통해 2부터 자신-1 숫자까지 %했을때 0이냐 1이냐를 구해 소수인지
>
> 확인하는 작업을 시켰습니다. [파일참조]
>
> 확실히 작은 숫자에서는 관계없으나 높은 숫자로 갈수록 소수인지 확인하기 위해
>
> 기나긴 계산이 이루어져야 한다는 거죠.[9자리쯤 되면 한참걸립니다 -_-]
>
> 소수 확인 알고리즘에 다른 방법이 없을까요? 좀 더 빠른 방법.
===============================================================================

3이상의 소수는 홀수이다....라는 특징을 이용해...연산시간을 좀 줄였습니다.

if문을 통해 입력값을 2로 나누었을때 나머지가 0이면 짝수이므로 소수확인연산을

처음부터 시작하지 않도록 하였고....나머지가 1이면 3부터 +2씩해나가며[3.5.7...]

나머지를 통해 소수인지 확인하는 작업을 거쳤습니다.

실제 같은 숫자로 돌려본 결과...

약 2배정도 빠르더군요......-ㅁ-;;

예) 1234567891[소수임] 을 첫번째 소스로 돌렸을때 1분 18초가량
두번째 소스로 돌렸을때 39초가량

두번째 소스도 올려봅니다.

Hit : 8300 Date : 2007/02/22 09:39