유

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

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

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


프로그램적으로 간단히 쓸수 있는 형태만 구현되었습니다.
최대 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건
+
제목 글쓴이 날짜 조회
11-10-25 조회 2,535
11-10-18 조회 4,092
11-10-18 조회 2,476
11-10-15 조회 3,671
11-10-10 조회 2,749
11-10-02 조회 2,637
11-09-28 조회 2,447
11-09-24 조회 2,538
11-09-22 조회 2,446
11-09-05 조회 2,924
11-08-31 조회 2,326
11-08-31 조회 2,631
11-08-31 조회 2,487
11-08-29 조회 3,025
11-08-28 조회 2,509
11-08-25 조회 2,569
11-08-17 조회 2,274
11-08-16 조회 2,519
11-08-11 조회 2,988
11-08-07 조회 2,689
11-08-03 조회 2,401
11-07-22 조회 2,141
11-07-12 조회 3,353
11-06-27 조회 2,121
11-06-01 조회 1,788
11-05-17 조회 2,595
11-05-01 조회 2,645
11-04-28 조회 2,942
11-04-28 조회 2,992
11-04-13 조회 2,658
11-03-27 조회 2,776
11-03-27 조회 2,661
11-03-14 조회 2,065
11-03-02 조회 2,392
11-03-02 조회 2,614
11-02-27 조회 3,041
11-02-23 조회 2,418
11-02-19 조회 2,565
11-02-14 조회 4,171
11-02-03 조회 2,955
11-01-24 조회 3,910
11-01-04 조회 2,439
10-12-08 조회 5,465
10-11-15 조회 2,466
10-11-14 조회 2,664
10-11-14 조회 3,677
10-10-29 조회 3,732
10-10-19 조회 2,750
10-10-07 조회 2,580
10-10-05 조회 4,502
10-09-18 조회 2,794
10-09-18 조회 2,539
10-09-17 조회 4,942
10-09-15 조회 2,878
10-09-15 조회 2,411
10-09-15 조회 2,900
10-09-15 조회 2,732
10-09-11 조회 4,063
10-09-11 조회 2,558
10-09-11 조회 2,610
10-09-07 조회 3,887
10-09-07 조회 3,420
10-08-29 조회 2,867
10-07-01 조회 3,132
10-06-30 조회 2,528
10-06-30 조회 2,713
10-06-30 조회 3,051
10-06-13 조회 2,107
10-04-15 조회 3,274
10-04-04 조회 3,506
10-02-23 조회 3,620
10-02-09 조회 3,191
10-01-25 조회 2,709
10-01-25 조회 2,808
09-12-27 조회 4,455
09-11-23 조회 3,676
09-11-20 조회 4,912
09-08-30 조회 3,114
09-08-30 조회 3,108
09-08-12 조회 3,083
09-07-22 조회 4,138
09-07-22 조회 4,783
09-07-15 조회 5,933
09-07-11 조회 3,014
09-06-17 조회 2,752
09-06-15 조회 3,045
09-05-29 조회 3,344
09-05-11 조회 5,967
09-05-08 조회 2,722
09-04-30 조회 3,847
09-04-17 조회 3,158
09-04-04 조회 3,351
09-03-05 조회 3,721
09-02-09 조회 3,702
09-02-03 조회 6,189
08-12-27 조회 3,253
08-12-20 조회 4,333
08-11-21 조회 5,290
08-11-14 조회 2,867
08-11-03 조회 3,342