현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

자연수 n이 소수인지 아는방법을 알고 싶습니다.

nabal의 이미지
글쓴이: nabal / 작성시간: 토, 2005/04/23 - 1:16오후

소수를 찾는 방법중에 제가 아는건 '에라스토테네스의 체' 밖에 없습니다. :oops: 여러가지 다른 방법이 있을텐데 아시는 분들은 답글 달아주시면 감사하겠습니다.

Forums: 
프로그래밍 QnA
yui의 이미지

글쓴이: yui / 작성시간: 토, 2005/04/23 - 2:00오후

코드 놀이터에 토끼군님이 올리신 소수 판정 알고리듬이 있었던 걸로 기억합니다. 참고해보세요.

SoftOn의 이미지

글쓴이: SoftOn / 작성시간: 토, 2005/04/23 - 3:01오후

http://no-smok.net/nsmk/PrimalityTestIsP

웃는 남자의 이미지

글쓴이: 웃는 남자 / 작성시간: 토, 2005/04/23 - 4:39오후

2의배수,3의배수,4의배수,.. 등을 걸러내는 방식의
에라토네스의 체에 의한 방법은 큰 수에 대해서는
계산량과 계산에 필요한 메모리가 너무 필요하므로
큰 수에 대한 소수판별에 사용하기에는 부적합니다.
실제로는 소수판정에 대한 효율성을 높이기 위해 정확한 소수판별을 포기하고
높은 확률로 소수인지 아닌지를 판단합니다.

확률적으로 소수를 판정하는 방법으로 간단한 Fermet 판정법이 있으나 완전하지는 않습니다.
그외 Miller 소수판별법은 Fermet 소수판정법보다 높은 확률로 소수를 판정할수 있습니다.

각 판별법에 대한 자세한 내용은 수학관련서적이나 논문을 찾아보시면 됩니다.
Primality Testing 검색어로 구글링해보시면 많은 정보를 얻을수 있으실꺼에요.

----------------------------------------
Nothing left after Nirvana.

둘러보기