유

간단한 자릿수의 소수 구하기

사용상에는 아무런 제한이 없습니다.
출처를 밝히고 퍼가는 것도 아무런 제한이 없습니다.
단, 교육(강좌)의 내용이나 출판(책)의 내용으로 포함되거나 인용 될수 없습니다

소수를 구하는 방법은 여러가지가 있습니다만
자리수가 클수록 구현의 어려움과 시간적인 문제가 발생합니다.


프로그램적으로 간단히 쓸수 있는 형태만 구현되었습니다.
최대 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% 정도 속도 개선이.. ^^
네 맞습니다. 한번만 하면 되니까요
원래 그렇게 했엇는데
잘 못 적은 부분이 있어서 바꾸면서
또 그렇게 바뀌엇네요

프로그램 구현상 그게 더 좋습니다.
댓글을 작성하시려면 로그인이 필요합니다.

프로그램

8,187건
+
제목 글쓴이 날짜 조회
12-04-06 조회 3,034
12-04-06 조회 3,251
12-04-05 조회 3,677
12-04-05 조회 3,066
12-04-05 조회 4,715
12-04-05 조회 3,370
12-04-05 조회 4,049
12-04-04 조회 4,347
12-04-04 조회 3,984
12-04-03 조회 3,315
12-04-03 조회 3,893
12-04-03 조회 3,205
12-04-03 조회 2,935
12-04-02 조회 3,643
12-04-02 조회 3,351
12-04-01 조회 3,270
12-04-01 조회 3,106
12-04-01 조회 3,327
12-03-31 조회 3,183
12-03-31 조회 3,663
12-03-30 조회 3,274
12-03-30 조회 2,915
12-03-30 조회 3,584
12-03-30 조회 3,257
12-03-30 조회 3,930
12-03-30 조회 3,389
12-03-29 조회 6,138
12-03-29 조회 3,943
12-03-29 조회 4,679
12-03-29 조회 3,147
12-03-28 조회 2,742
12-03-28 조회 3,460
12-03-28 조회 4,381
12-03-28 조회 3,175
12-03-27 조회 4,678
12-03-27 조회 3,089
12-03-27 조회 3,474
12-03-26 조회 4,162
12-03-26 조회 3,547
12-03-26 조회 3,124
12-03-26 조회 3,853
12-03-26 조회 6,210
12-03-25 조회 2,803
12-03-25 조회 2,958
12-03-24 조회 3,029
12-03-24 조회 6,491
12-03-24 조회 3,657
12-03-24 조회 3,915
12-03-23 조회 3,868
12-03-23 조회 3,049
12-03-23 조회 2,944
12-03-23 조회 3,081
12-03-22 조회 3,934
12-03-22 조회 3,325
12-03-22 조회 3,570
12-03-22 조회 4,794
12-03-22 조회 3,274
12-03-22 조회 3,738
12-03-22 조회 3,624
12-03-22 조회 2,907
12-03-22 조회 5,816
12-03-22 조회 3,562
12-03-22 조회 5,110
12-03-21 조회 3,331
12-03-21 조회 3,126
12-03-21 조회 3,227
12-03-21 조회 2,919
12-03-21 조회 3,620
12-03-21 조회 3,613
12-03-21 조회 4,944
12-03-21 조회 6,500
12-03-21 조회 2,883
12-03-20 조회 5,691
12-03-20 조회 2,873
12-03-20 조회 3,390
12-03-20 조회 3,139
12-03-20 조회 3,394
12-03-20 조회 4,154
12-03-19 조회 3,622
12-03-19 조회 2,852
12-03-19 조회 3,537
12-03-18 조회 3,265
12-03-17 조회 3,584
12-03-17 조회 4,166
12-03-17 조회 3,397
12-03-16 조회 3,003
12-03-16 조회 4,164
12-03-16 조회 3,404
12-03-15 조회 3,018
12-03-15 조회 3,094
12-03-15 조회 3,415
12-03-15 조회 2,816
12-03-14 조회 4,039
12-03-14 조회 3,293
12-03-14 조회 3,352
12-03-14 조회 2,998
12-03-13 조회 3,660
12-03-13 조회 4,526
12-03-13 조회 2,870
12-03-13 조회 2,807