<?php

set_time_limit(0);
ini_set('memory_limit','1G');
header('Content-Type: text/html; charset=utf-8');



/*

※ 포인트

큰 수의 소수 판별에는 많이 시간이 필요하다.
최대한 적은 횟수의 루프로 시간을 단축하는 것이 포인트
10자리의 수는 숫자형의 범위를 넘어선다.(2147483647)
따라서 bcmod 사용


정확한 소수판별법은 2002년에 인도 수학자들에 의해 발견 되었으나
수식이 난해하여 수학과 전공자가 아니면 이해하기 힘들거 같고,
10자리 정도의 작은수라면 오히려 앞에서 부터 순차비교하는 것이 더 빠를수 있을것 같다.



※ 알고리즘

중복되지 않는 숫자들로 구성된 수(0, 1, 2, 3, 4, 5, 6, 7, 8, 9 를 사용)로 된 자연수의 모든 경우의 수중 가장 큰 수는 9876543210 이다
소수 판별시 비교되는 소수는 판별할 수의 제곱근 값을 넘을수 없다.

그러나, 숫자자체는 10자리 이하로 작은 수이지만 앞에서 부터 일일이 비교해야 하기 때문에
메모리 문제가 발생하거나 좀 느릴수 있다.

*/



$array = range(9, 0);
$array1 = range(9, 1);

$max = floor(sqrt(9876543210));//나올수 있는 경우의 수중 제일 큰값의 제곱근 값, 비교할 소수는 $max 를 넘을수 없다.
$prime = get_prime ($max);
//print_r($prime);



function get_prime ($end) {//$end 까지의 소수를 구한다.

    $end = ($end > 100000) ? 100000 : $end;//자리수가 크면 느려서 제한

    $prime = Array(2);
    for ($search = 3; $search <= $end; $search += 2) {

        if (check_prime ($prime, $search) == true)
            $prime[] = $search;
    }

    return $prime;
}



function check_prime ($prime, $search) {

    if (in_array($search, $prime))
        return true;

    $max = floor(sqrt($search));
    foreach($prime as $p){

        if ($p < 3) {//홀수만 비교하므로 1 과 2는 따질 필요가 없다.

            continue;
        }
        else if ($p > $max) {//비교를 위해 대입하는 소수가 비교되는 수의 제곱근보다 클수 없다.

            return true;
        }
        else {//2147483647 범위를 넘는 숫자가 있을수 있으므로

            if (is_int($search)) {//숫자형

                if ($search % $p == 0) //다른소수의 배수이므로 소수가 아니다.
                    return false;
            }
            else {//문자형

                if (bcmod($search, (string)$p)  == 0) //다른소수의 배수이므로 소수가 아니다.
                    return false;
            }
        }
    }

    return true;
}



foreach($array1 as $key1 => $a){//첫째자리는 0 이 없어야 열자리 수를 구할수 있다.

    $array2 = $array;
    unset($array2[$key1]);

    foreach($array2 as $key2 => $b){

        $array3 = $array2;
        unset($array3[$key2]);

        foreach($array3 as $key3 => $c){

            $array4 = $array3;
            unset($array4[$key3]);

            foreach($array4 as $key4 => $d){

                $array5 = $array4;
                unset($array5[$key4]);

                foreach($array5 as $key5 => $e){

                    $array6 = $array5;
                    unset($array6[$key5]);

                    foreach($array6 as $key6 => $f){

                        $array7 = $array6;
                        unset($array7[$key6]);

                        foreach($array7 as $key7 => $g){

                            $array8 = $array7;
                            unset($array8[$key7]);

                            foreach($array8 as $key8 => $h){

                                $array9 = $array8;
                                unset($array9[$key8]);

                                foreach($array9 as $key9 => $i){

                                    $array10 = $array9;
                                    unset($array10[$key9]);

                                    foreach($array10 as $key10 => $j){

                                        if ($j % 2 == 0)
                                            continue;

                                        $number = (string)$a . (string)$b . (string)$c . (string)$d . (string)$e . (string)$f . (string)$g . (string)$h . (string)$i . (string)$j;

                                        if (check_prime ($prime, $number) === true)
                                            break 10;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

echo "구성 요소가 서로 중복되는 숫자가 없는 숫자 중에서 가장 큰 소수는 얼마일까요 ? <br />" . PHP_EOL;

echo $number;

?>

저도 실수가 있엇네요

bcmod 을 인자를 꺼꾸로 써서 수정하였습니다.

그리고 저도 이것이 불완전 해서 다시 수정해서

새로 올리도록 하겠습니다.

$i = 9876543211;  // 초기값
while (1) {
    $i -= 2; // 홀수를 검토한다.
    $flag = true;
    $str = (string) $i;
    for ($k = 0; $k < strlen($str); $k++) {  //  중복되는 숫자 체크
        $arr[$str[$k]] += 1;
        if ($arr[$str[$k]] > 1) {
            $flag = false;
            break;
        }
    }
    unset($arr);
    if ($flag == false) continue;

    $max = (int) (sqrt($i));
    for ($j = 3; $j < $max; $j += 2) {
        if ($i % $j == 0) {
            $flag = false;
            break;
        }
    }
    if ($flag == true) break;
}
echo $i;  // 9876541203

일단 이것은 계산이 제대로 되지 않는 것 같습니다.

이유는

9876543211 은 2147483647 보다 크기 때문에

bc 관련 함수를 사용하여야 정확합니다.

예로

<?php

$i = 9876543211;

echo ($i % 3) . "<br />";

echo bcmod((string)$i, '3');

?>

또는

<?php

echo (9876543211 % 3) . "<br />";

echo bcmod('9876543211', '3');

?>

실행하여 보면 값이 2 와 1 으로 서로 다른 값이 출력 됨을 알수 있습니다.

직접 손으로 나누어 보아도 값이 1 임을 알수 있습니다.

실행시 오류가 안나서 생각지 못한 부분인데
정수형의 범위를 벗어나는군요.
다시 생각해봐야 겠습니다.

두번째의 문제점은

루프의 회수입니다.

중복되지 않는 수로 만들어진 10 자리의 수를 큰수부터 아래로 내려가는 것은 저와 동일합니다.

그러나

소수판별에 있어서

그 수의 제곱근 까지 모든 홀수를 루프 돌려서 나누어 볼필요는 없습니다.

그 이하의 소수로만 나누어 보면 됩니다.

실제로 100000 이하의 소수는 9천여개 밖에 되지 않습니다.

10000000000 의 제곱근 값은 100000 입니다.

그 이하의 수의 소수 판별에는 각 수당 최대 9천 여회를 돌면 되지만

for ($j = 3; $j < $max; $j += 2) {

    if ($i % $j == 0) {

        $flag = false;
        break;
    }
}

이 방법은

10000000000 이라고 햇을때 5만번을 돌아야 합니다.

저의 경우도 맨처음에 나누기 위한 소수를 구할때

같은 방법이 사용되지만

그것은 배열로서 저장되어 재사용 되므로

최초에 한번만 그런 식으로 루프가 돌고

그다음 부터는 구해진 소수로서만 돌기 때문에 횟수가 엄청나게 많이 줄어듭니다.

개선점에 대한 자세한 설명 감사합니다.

중복되지 않는 수 구하는 방법

    $flag = true;
    $str = (string) $i;
    for ($k = 0; $k < strlen($str); $k++) {  //  중복되는 숫자 체크
        $arr[$str[$k]] += 1;
        if ($arr[$str[$k]] > 1) {
            $flag = false;
            break;
        }
    }
    unset($arr);

이 부분은 참 좋은 것 같습니다.

감사합니다. ^^

일단 10자리중에서는 조건을 만족하는 소수는 없네요.

<?php

set_time_limit(0);
ini_set('memory_limit','1G');
header('Content-Type: text/html; charset=utf-8');



function microtime_float() {

    list($usec, $sec) = explode(" ", microtime());
    return (((float)substr((string)$usec, 0, 4) + (float)$sec)) * 1000;
}



function get_excute_time($msg, $start_time){

    $end_time = microtime_float();
    $time = ($end_time - $start_time) / 1000;

    echo "$msg : $time seconds" . PHP_EOL ;
}



//주어진 숫자까지 포함된 모든 소수를 구함
function get_prime ($end) {

$end = (int)$end;
    $end = ($end > 100000) ? 100000 : (($end <= 10) ? 10 : $end); //100000 보다 크면 100000, 10보다 작거나 같으면 10

    $prime = Array(2, 3, 5, 7);

    if ($end == 10) {

        return $prime;
    }

    for ($search = 11; $search <= $end; $search += 2) { //홀수만 대입

        if (substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐, 직접 나누는것보다 끝자리만 확인하는것이 더 빠를것 같아 처리
            continue;

        if (check_prime ($prime, $search) == true)
            $prime[] = $search;
    }

    return $prime;
}



//주어진 숫자까지 포함된 모든 소수를 구함
function get_prime2 ($prime, $start, $end) {

$end = (int)$end;
    $end = ($end > 100000) ? 100000 : $end; //100000 보다 크면 100000

    if ($start >= $end)
        return $prime;

    if ($start % 2 == 0)
        $start++;

    for ($search = $start; $search <= $end; $search += 2) { //홀수만 대입

        if (substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐, 직접 나누는것보다 끝자리만 확인하는것이 더 빠를것 같아 처리
            continue;

        if (check_prime ($prime, $search) == true)
            $prime[] = $search;
    }

    return $prime;
}



//기존에 가진 소수 배열로서 소수인지 판별
function check_prime ($prime, $search) {

$search = (float)$search;//float(double) 형으로 형변환

    if ($search > 2 && (int)substr((string)$search, -1) % 2 == 0)// 2보다 큰 자연수 중에 0, 2, 4, 6, 8로 끝나는 소수는 없다. 모두 2로 나누어짐
        return false;

    if ($search > 5 && substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐
        return false;

$max = bcsqrt((string)$search, 1);//결과값이 문자형으로 반환, $search 가 2147483647 보다 클수 있으므로 bcsqrt

if (strpos($max, '.') === false) {//$search 는 $max 의 제곱이라는 의미

//echo "$search $max 제곱근" . PHP_EOL;
return false;
}

    $max = (int)$max; //정수형으로 변환, 소수점 이하 버려짐
    foreach($prime as $p){

        if ($p > $max) {//비교를 위해 대입하는 소수가 비교되는 수의 제곱근보다 클수 없다.

            return true;
        }
        else if (bcmod($search, (string)$p)  == 0) {//다른소수의 배수이므로 소수가 아니다. $search 가 2147483647 보다 클수 있으므로 bcmod

//echo "$search $p 의 배수" . PHP_EOL;
return false;
        }
    }

    return true;
}



//기존에 가진 소수 배열로서 소수인지 판별
function check_prime2 ($prime, $search, $start) {

$search = (float)$search;//float(double) 형으로 형변환

    if ($search > 2 && (int)substr((string)$search, -1) % 2 == 0)// 2보다 큰 자연수 중에 0, 2, 4, 6, 8로 끝나는 소수는 없다. 모두 2로 나누어짐
        return false;

    if ($search > 5 && substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐
        return false;

$max = bcsqrt((string)$search, 1);//결과값이 문자형으로 반환, $search 가 2147483647 보다 클수 있으므로 bcsqrt

if (strpos($max, '.') === false) {//$search 는 $max 의 제곱이라는 의미

//echo "$search $max 제곱근" . PHP_EOL;
return false;
}

    $max = (int)$max; //정수형으로 변환, 소수점 이하 버려짐
    foreach($prime as $p){

        if ($start > $p)
            continue;

        if ($p > $max) {//비교를 위해 대입하는 소수가 비교되는 수의 제곱근보다 클수 없다.

            return true;
        }
        else if (bcmod($search, (string)$p)  == 0) {//다른소수의 배수이므로 소수가 아니다. $search 가 2147483647 보다 클수 있으므로 bcmod

//echo "$search $p 의 배수" . PHP_EOL;
return false;
        }
    }

    return true;
}



function find_prime($number) {

    global $prime_tiny, $prime_small, $prime_middle, $prime_big;

    if (check_prime ($prime_tiny, $number) === true) {

        if (check_prime2 ($prime_small, $number, 11) === true) {

            if (check_prime2 ($prime_middle, $number, 101) === true) {

                if (count($prime_big) == 0) {

                    $start_time2 = microtime_float();
                    $max =  (int)bcsqrt($number, 1);
                    $prime_big = get_prime2($prime_middle, 1001,$max); //비교가능한 최대의 소수까지 구함
                    get_excute_time("prime_big 을 구한 시간", $start_time2);
                }

                if (check_prime2 ($prime_big, $number, 1001) === true) {

                    return $number;
                }
            }
        }
    }

    return false;
}



$start_time = microtime_float();

$prime_tiny = get_prime(10); //기본적인 체크를 위한 작은 소수들을 구함
get_excute_time("prime_tiny 까지 구한 시간", $start_time);

$prime_small = get_prime2($prime_tiny, 11, 100); //기본적인 체크를 위한 작은 소수들을 구함
get_excute_time("prime_small 까지 구한 시간", $start_time);

$prime_middle = get_prime2($prime_small, 101, 1000); //기본적인 체크를 위한 작은 소수들을 구함
get_excute_time("prime_middle 까지 구한 시간", $start_time);

$prime_big = Array();

$array = range(9, 0);
$array1 = range(9, 1);

foreach($array1 as $key1 => $a){//첫째자리는 0 이 없어야 열자리 수를 구할수 있다.

    $array2 = $array;
    unset($array2[$key1]);

    foreach($array2 as $key2 => $b){

        $array3 = $array2;
        unset($array3[$key2]);

        foreach($array3 as $key3 => $c){

            $array4 = $array3;
            unset($array4[$key3]);

            foreach($array4 as $key4 => $d){

                $array5 = $array4;
                unset($array5[$key4]);

                foreach($array5 as $key5 => $e){

                    $array6 = $array5;
                    unset($array6[$key5]);

                    foreach($array6 as $key6 => $f){

                        $array7 = $array6;
                        unset($array7[$key6]);

                        foreach($array7 as $key7 => $g){

                            $array8 = $array7;
                            unset($array8[$key7]);

                            foreach($array8 as $key8 => $h){

                                $array9 = $array8;
                                unset($array9[$key8]);

                                foreach($array9 as $key9 => $i){

                                    $array10 = $array9;
                                    unset($array10[$key9]);

                                    foreach($array10 as $key10 => $j){

                                        if ($j % 2 == 0 || $j == 5)// 2로 나누어지거나 5이면 통과
                                            continue;

                                        $number = (string)$a . (string)$b . (string)$c . (string)$d . (string)$e . (string)$f . (string)$g . (string)$h . (string)$i . (string)$j;//10자리

                                        if (find_prime($number) !== false) {

                                            get_excute_time("결과 까지 걸린 시간", $start_time);
                                            echo $number;
                                            exit;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

foreach($array1 as $key1 => $a){//첫째자리는 0 이 없어야 열자리 수를 구할수 있다.

    $array2 = $array;
    unset($array2[$key1]);

    foreach($array2 as $key2 => $b){

        $array3 = $array2;
        unset($array3[$key2]);

        foreach($array3 as $key3 => $c){

            $array4 = $array3;
            unset($array4[$key3]);

            foreach($array4 as $key4 => $d){

                $array5 = $array4;
                unset($array5[$key4]);

                foreach($array5 as $key5 => $e){

                    $array6 = $array5;
                    unset($array6[$key5]);

                    foreach($array6 as $key6 => $f){

                        $array7 = $array6;
                        unset($array7[$key6]);

                        foreach($array7 as $key7 => $g){

                            $array8 = $array7;
                            unset($array8[$key7]);

                            foreach($array8 as $key8 => $h){

                                $array9 = $array8;
                                unset($array9[$key8]);

                                foreach($array9 as $key9 => $i){

                                    if ($i % 2 == 0 || $i == 5)// 2로 나누어지거나 5이면 통과
                                        continue;

                                    $number = (string)$a . (string)$b . (string)$c . (string)$d . (string)$e . (string)$f . (string)$g . (string)$h . (string)$i;//9자리

                                    if (find_prime($number) !== false) {

                                        get_excute_time("결과 까지 걸린 시간", $start_time);
                                        echo $number;
                                        exit;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

get_excute_time("결과 까지 걸린 시간", $start_time);

?>

prime_tiny 까지 구한 시간 : 0 seconds
prime_small 까지 구한 시간 : 0 seconds
prime_middle 까지 구한 시간 : 0.01 seconds
prime_big 을 구한 시간 : 0.89 seconds
결과 까지 걸린 시간 : 19.29 seconds
987654103

일단 결과는 만족할 만 합니다.

사용된 알고리즘은

1. 소수를 구할때
2보다 큰 소수에는 짝수는 없다.
5보다 큰 소수에는 5로 끝나는 수는 없다.
판별할 수의 제곱근 값이 정수로 딱 떨어지면 소수가 아니다.
판별할 수의 제곱근 값보다 작거나 같은 소수까지만 비교한다.

2. 숫자자체가 크고 범위가 넓기 때문에
비교하는 소수의 영역을 작은것부터 해서 빠르게 제외시킬것은 제외

3. 소수를 뽑아올때나 비교할때 중복 계산은 생략

4. 숫자가 크기 때문에 9876543210 부터 -2 씩 내려 가는 비교방식 보다는
나올수 있는 경우의 수를 뽑는것이 훨씬 적으므로 그 방식을 유지

5. 10자리 내에서 먼저 해보았으나 결과가 없어 9자리 까지 확대



10자리와 9자리의 경우의 수를 구하는 부분을 재귀함수 등으로 만들고 싶었으나
시간 문제도 있고 이정도면 충분할것 같아 마무리 했습니다.



핵심
루프는 최대한 작게
조건 맞는 수를 찾는 부분이므로
조건이 작은 것부터 체크해서 맞지 않는 것은 빠르게 제외

사실 일정정도의 작은수 같은 경우에는
어떻게 하든 빠른 시간안에 답이 나오지만
이렇게 일정정도 이상의 수는
제대로 된 알고리즘이 필요합니다.

좋은 문제였다고 생각하며,
교재로 사용해도 좋을 것 같습니다.

수고 하셨습니다.
범위가 커서 그런지  테스트 해보니  cpu 가 몸살이 날려고 하네요.

네 감사합니다.
슈와이님도 고생하셧습니다.

제가 시스템적으로는 잘 모르지만
1회의 루프의 범위가 크면
메모리를 자동으로 충분히 많이 할당하고 시작하는것 같습니다.
cpu도 루프가 끝날때까지 계속 계산해 대는 것 같구요.

슈와이님도 범위를 쪼개서 10000 개 이내에서 돌려서 찾고 돌려서 찾고
를 반복하는 방법을 한번 고려해 보시는게 어떨까 생각합니다.

고맙습니다. ^^