[PHP] n번째까지의 소수 구하기

1. 소수란?

약수가 1과 자기자신밖에 없는 수를 말함.

ex) 2, 3, 5, 7, 11 .....

2. 소수 구하는 방법 (알고리즘)

1을 제외한 어떠한 자연수로 나누어진다면, 그 수는 소수가 아닌것이다.

2 => 1, 2 (소수)

3 => 1, 3 (소수)

4 => 1, 2, 4

5 => 1, 5 (소수)

6 => 1, 2, 3, 6

위에서는 1과 본인 둘밖에없는 2, 3, 5가 소수이다.

좀 더 높은 숫자로 비교를 해보자

13 => 1, 13 (소수)

15 => 1, 3, 5, 15

16 => 1, 2, 4, 8, 16

19 => 1, 19 (소수)

26 => 1, 2, 13, 26

35 => 1, 5, 7, 35

위에서 자세히 들여다보면 소수가 아닌 숫자들은 모두 소수와 나누어지는 것을 확인할 수 있다.

15 => 3, 15

16 => 2

26 => 2, 13

35 => 5, 7

이처럼 소수가 아닌 모든 자연수는 소수와 나누어 떨어지게끔 되어 있다.

이제 이 알고리즘을 코딩에 적용시켜보도록 하자

function get_prime($num){

    $a = 2;

    $arr = array(2);

    while(sizeof($arr)<$num){

        

        for($j=0; $j<sizeof($arr); $j++){

            if($a%$arr[$j]==0) break;

            if($j == sizeof($arr)-1) $arr[] = $a;

        }

        $a++;

    }

    return $arr;

}

print_r(get_prime(10));

결과