간단한 자릿수의 소수 구하기
사용상에는 아무런 제한이 없습니다.
출처를 밝히고 퍼가는 것도 아무런 제한이 없습니다.
단, 교육(강좌)의 내용이나 출판(책)의 내용으로 포함되거나 인용 될수 없습니다
소수를 구하는 방법은 여러가지가 있습니다만
자리수가 클수록 구현의 어려움과 시간적인 문제가 발생합니다.
프로그램적으로 간단히 쓸수 있는 형태만 구현되었습니다.
최대 5자리의 소수까지 구해집니다.
만약 자릿수를 4로 설정햇다면
1000 부터 9999 까지의 소수를 구해줍니다.
<?
//지정된 자리수에 존재하는 소수 전체를 배열로 반환합니다. max len = 5
function get_simple_prime_number($len=5){
$len = abs((int)$len);
if ($len < 1) $len = 1;
else if ($len > 5) $len = 5;
$prime_1 = Array(1, 2, 3, 5, 7);
if ($len == 1) return $prime_1;
$start = pow(10, ($len - 1)) + 1;//101
$end = pow(10, $len) - 1;//999
$prime = $prime_1;
unset($prime[0]);//1제거
unset($prime[1]);//2제거
$array = Array();
for($i = 11; $i <= $end; $i+=2){//10보다 큰 소수에는 짝수가 없다.
$max = floor(sqrt($i));
foreach($prime as $j) {
if ($j > $max) break;
if ($i % $j == 0) continue 2;
}
$prime[] = $i;
if ($i >= $start) $array[] = $i;
}
return $array;
}
print_r( get_simple_prime_number(5));
?>
소수를 구하는 알고리즘을 구현하는 방법에는 크게 두가지가 잇습니다.
1. 범위의 숫자를 모두 저장한후 소수가 아닌것은 제거 하는 방법
2. 앞에서 부터 순차적으로 비교하여 소수인것만 저장하는 방법
저는 2번의 방식을 사용했으며,
총 3가지의 알고리즘이 포함되었습니다.
1. 10보다 큰 소수 에는 홀수만 존재한다. (뒷자리가 1, 3 7, 9 만 존재합니다.)
작은수에선 디테일한 비교가 오히려 전체 속도에서 느려질수 있어서 5를 제거 하는 부분은 뺏습니다.
2. 소수의 배수는 소수가 아니다.
3. 현재 비교하고자 하는 숫자가 소수인지 판별하기 위해서 대입하는 소수의 범위가
현재 숫자의 제곱근 값을 넘을수 없다.
등입니다.
|
댓글을 작성하시려면 로그인이 필요합니다.
댓글 5개
이런 방법도 있던데..
요건 에라토스테네스의 체 라는 방법입니다.
저도 검색해서 찾아냈어요
function sieve($end) {
$prime=array();
for( $a = 2; $a*$a <= $end; $a++) {
if($prime[$a] == 0) {
for($b = a*2; $b<=$end; $b+=$a) $prime[$b] = 1;
}
}
return $prime;
}
어떤수가 소수이면 그의 배수는 소수가 아니라는 것에 착안하여 소수를 찾아내는 방법입니다.
pow()로 비교하는 부분을, $prime loop 밖으로 빼는 것이 속도 개선에 도움이 될것 같습니다.
loop 밖에서 sqrt로 계산해 저장해 놓고 loop 안에서는 그 값과 $j를 비교하는 식으로요..
제 놋북에서 비교해보니까, 5자리 계산시 50% 정도 속도 개선이.. ^^
원래 그렇게 했엇는데
잘 못 적은 부분이 있어서 바꾸면서
또 그렇게 바뀌엇네요
프로그램 구현상 그게 더 좋습니다.