소수[솟수] 쉽게 구하기

PHP기준으로 설명드리겠습니다.

자, 컴퓨터는 1억번의 for문[반복문]을 1초에 실행할수 있습니다.

보통 소수구하는것은 아래와 같이 쓰죠.

예 저 노가다합니다. ㅡ,.ㅡ;;

for($i=2;$i <= 1000;$i++)
{
for($j=2;$j <=i;$j++)
{
if($i %$ j == 0)
{
$cnt++;
}
}
if($cnt != 1)
{
echo "$i 는 소수가 아닙니다.";
}
$cnt = 0;
}

뭐..더 쉬운방법도 있겠지만 보통 위와같이 씁니다.

1000정도는 금방할수있겠지만 100만이 넘을경우 1초가 넘어가는 경우가 있습니다.

1초가 넘는것쯤이야 PHP에서는 간단할지몰라도 c++로

프로그래밍 대회에 나가는경우에는 제한이 1초입니다.

그러므로 소수를구할때는 소수의 최적화인 에라토스테네스의 해를 사용하는것이 가장 좋습니다.

그럼, 에라토스테네스의 해 알고리즘을 보도록하죠.

먼저 배열을 하나 잡아놓습니다.

그리고 2[배열번호]에는 0을 넣어놓습니다.

그후 for문을 2부터 원하는수까지 돌립니다.

그리고, 만약 배열의 i[for문 변수]번째방에 있는 값이 1이 아니라면

i의 배수방을 모두 1로 바꿔줍니다.

주의 : i번쨰 방은 0으로 넣어주세요.

그런식으로 계속 반복을 해나가면 훨씬 수월하게 소수[솟수]를 구할수 있을겁니다.

경우의 수 구하기 ---

타일채우기 문제와 비슷합니다.

대충 문제를 살펴보면

2 * n크기의 판이 있다. 그 판에 타일을 채우려고한다.
타일의 종류는 세로로 2*1타일, 가로로 2*1타일과 2*2타일이 있다.

이 세가지 타일로 모두 채울수 있는 경우를 알아내어라.

이 문제..

입출력 예를 봅시다.

입력
2
8
12
출력
3
171
2731

이 문제를 풀기는 좀 복잡할거같지 않습니까?

전혀 그렇지 않습니다.

2진수를 사용하면 아주 간편한 방법으로 문제를 풀수 있습니다.

알고리즘은 아래와 같습니다.

예를들어.. 수가 7이라면 7-1, 즉 6번까지

1010...이런식으로 반복을 해나갑니다.
그리고 맨마지막 7번째 수는 1로 합니다.

그러면 수가 아래와같이 되겠죠.

1010101

위와 같이 한것을 10진수로 바꾸면 답이 됩니다.

즉,

짝수 8을 또 예로 보면

8-1,즉 7번까지 2진수로 1010을 반복하면

1010101

위와같이 되죠.

그 뒤에 1을 붙이면

10101011

이 됩니다.

이 수를 10진수로 바꾸시면 답인 171이 나옵니다.

이렇게 문제를 이리 굴려보고 저리 굴려보고 생각을 해보면

최적해와 최소의 시간, 그리고 쉬운방법으로 문제를 풀수 있습니다.

그럼, 이상 타키의 허접팁이였습니다.