서로 다른 숫자로 구성된 가장 큰 소수

<?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);

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

감사합니다. ^^

와 정말 다들 너무 대단하십니다...

두분의 코딩에 감탄에 감탄을 ++ 하고 있었네요.


제가 알고 있는 소수 구하는 다른 방법을 하나더 소개합니다.

소수를 구하는 방법은 크게 2가지 정도로 나뉘는 것 같습니다.

유창화 님이 소개해주신 방법대로,
$num 이 소수인지 판단하기 위해서는 2부터 1 씩 더해가며 $num 의 제곱근까지 나누어보면 됩니다. 만약 나누었을때 그 나머지가 0 이 나오는 경우가 한번이라도 발견되면, 그 수는 소수가 아닌 것으로 판단 됩니다. 그리고 float($num 의 제곱근) 까지 나누었을 때까지 한번도 그 나머지가 0 인경우가 발견되지 않았다면 그 수는 소수로 판단됩니다.float($num 의 제곱근) 보다 큰 수로는 나누어볼 필요가 없지요, 그 이유는 float($num 의 제곱근) 보다 큰 수로 나누었을 경우 나머지가 0으로 딱 떨어진다면 그 몫은 float($num 의 제곱근) 보다 작은 수가 되기 때문에,, 이미 그 이전 계산 과정에서 발견이 되었기 때문입니다.

네 여기서 살짝 더 나아가, 1씩 더해가며 비교해보는 것이 아니라, 2를 제외한 모든 소수는 홀수라는 사실을 알기 때문에, 3부터 2씩 더해가며 float($num 의 제곱근)이하까지 비교해보면 되죠. 이것 또한 유창화님이 제시해주신 소스상에서 발견됩니다.

그리고 여기서 한단계 더 나아갈 수 있죠. "모든 홀수로 과연 다 나누어봐야 하는 것인가" 라는 문제입니다.
예를 들자면, 어떤 수가 소수인지 판단하기 위해 이 수를 9로 나누어봐야 하는 것인가? 만약 이 수가 9로 나누어진다면, 이 수는 이미 그 이전 계산 과정에서 3으로 나누어졌을 것입니다. 즉 3의 배수이면서 홀수인 9, 15, 21 등으로 나누어볼 필요가 없게 되지요. 마찬가지로, 5의 배수이면서 홀수인 15, 25, 35... 등으로도 나누어볼 필요가 없게 된다는 것을 알 수 있습니다.

즉, 결론적으로 어떤 수($num)가 소수인지 판단하기 위해서는 float($num의 제곱근) 이하의 모든 소수로 나누어보면 될듯합니다.
이것도 유창화님께서 언급해주셨습니다.

여기까지가 소수를 구하는 한가지 방법이었구요,

다른 한가지 방법을 소개하자면, "에라토스테네스의 채" 방법을 이용한 것입니다.
먼저 소개해드린 방식과 반대 방식인데요, 이전 방식은 그 수보다 작은 수와 비교했던 방식이라면, 이번 방식은 어떤 소수의 배수는 모두 제거하는 방식입니다.
즉 100000 이하의 모든 소수를 구하기 위해서
2 가 소수이므로, 2의 배수인 4,6,8,... 은 소수가 아닙니다.
3 이 소수이므로, 3의 배수인 6,9,12,15... 은 소수가 아닙니다.

이런 식으로 계산해가는 방식인데요.. 말로 설명하려니 어렵네요. 간단히 php 소스로 짜본 것을 소개합니다.



// '에라토스테네스의 채' 방법을 이용한 소수 구하는 방법
function getPrime($num) {

$arr = array();
$i = 2;

for ($i = 2; $i <= $num; $i++) {
$arr[$i] = 1;
}

for ($i = 2; $i <= $num; $i++) {
if ($arr[$i] == 0) { // 이것은 이미 어떤 수의 배수가 되었다는 의미
continue;
}
for ($j = $i * 2; $j <= $num; $j = $j + $i) { // $i 의 배수는 모두 소수가 아니므로 배열 값에 0 을 대입
$arr[$j] = 0;
}
}

// return
for ($i = 2; $i <= $num; $i++) {
if ($arr[$i] != 0) echo $i . ", ";
}
}
$num = 1000;
echo $num . " 이하의 모든 소수는 ";
getPrime(1000);
echo " 입니다";