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

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


프로그램적으로 간단히 쓸수 있는 형태만 구현되었습니다.
최대 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. 현재 비교하고자 하는 숫자가 소수인지 판별하기 위해서 대입하는 소수의 범위가
현재 숫자의 제곱근 값을 넘을수 없다.

등입니다.