간단한 자릿수의 소수 구하기
사용상에는 아무런 제한이 없습니다.
출처를 밝히고 퍼가는 것도 아무런 제한이 없습니다.
단, 교육(강좌)의 내용이나 출판(책)의 내용으로 포함되거나 인용 될수 없습니다
소수를 구하는 방법은 여러가지가 있습니다만
자리수가 클수록 구현의 어려움과 시간적인 문제가 발생합니다.
프로그램적으로 간단히 쓸수 있는 형태만 구현되었습니다.
최대 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. 현재 비교하고자 하는 숫자가 소수인지 판별하기 위해서 대입하는 소수의 범위가
현재 숫자의 제곱근 값을 넘을수 없다.
등입니다.
|
댓글을 작성하시려면 로그인이 필요합니다.
프로그램
태그 필터 (최대 3개)
전체
개발자
소스
기타
mysql
팁자료실
javascript
php
linux
flash
정규표현식
jquery
node.js
mobile
웹서버
os
프로그램
강좌
썸네일
이미지관련
도로명주소
그누보드5
기획자
견적서
계약서
기획서
마케팅
제안서
seo
통계
서식
통계자료
퍼블리셔
html
css
반응형
웹접근성
퍼블리싱
표준화
반응형웹
홈페이지기초
부트스트랩
angularjs
포럼
스크린리더
센스리더
개발자톡
개발자팁
퍼블리셔톡
퍼블리셔팁
기획자톡
기획자팁
프로그램강좌
퍼블리싱강좌
댓글 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% 정도 속도 개선이.. ^^
원래 그렇게 했엇는데
잘 못 적은 부분이 있어서 바꾸면서
또 그렇게 바뀌엇네요
프로그램 구현상 그게 더 좋습니다.