1부터 N까지의 소수를 출력하자…

이번에도 역시… Firen’s Diary의 화현님께서 내주신 문제입니다…
1부터 N까지의 소수를 출력하는것이고요…

조건은…

초급 : 없음
중급 : 소수를 배열에 넣어 처리, 단순한 방법보다 조금 더 빠른 속도로 동작하게…
고급 : Linked List사용, unsigned long이 지원하는 숫자까지 계산, 파일명을 입력받아 해당 파일로 결과 출력

입니다…

아직 문제를 풀지는 못했습니다…

다만 대충 윤곽은 잡은것 같네요…
일단 3가지의 성질을 이용합니다.

1. n이 큰 양의 정수일때 n보다 작거나 같은 양의 소수의 개수는
“n / log(n)” 입니다.2. n이 홀수 소수일 경우(즉, 2보다 큰 소수일 경우) 2^(n-1)-1은 n으로 나누어 집니다.
이 명제의 역은 성립하지 않으나, 성립하지 않는 경우는 거의 없고…
따라서 2^(n-1)-1 / n 이 나누어 떨어진다면 n은 소수일 가능성이 매우 높습니다…
(만약 역이 성립하지 않는다 하여도… 2^(n-1)-1 / n이 나누어 떨어진다면 소수일 확률이 있습니다…
반대로 2^(n-1)-1 / n로 나누어 떨어지지 않는다면 소수가 아닙니다…)

3. n은 root(n)보다 작은 소인수 P를 항상 가진다는 합성수의 성질에 따라…
n이 소수인지 검증하려면 최대정수 root(n)으로 나누어 보면 됩니다…
이때 모두 나누어 떨어진다면 n은 소수입니다.

따라서… 한개의 재귀함수를 사용하고… n/log(n)개의 원소를 가지는 배열을 사용합니다…

첫번째 함수는…
2의 성질을 이용하는 함수로…
입력받은 수 n’이 소수인 확률이 있는지 검사합니다…
이때 n’은 3부터 n까지의 모든 정수입니다…
n’이 소수일 가능성이 있는 경우 두번째 함수를 호출합니다…
두번째 함수에서 소수라고 판정되었을 경우(1이 리턴되었을 경우) n’을 배열에 저장하고…
n’에 1을 더해 재귀호출하고
소수가 아니라고 판정되었을 경우(0이 리턴되었을경우) 그냥 n’에 1을 더해 재귀호출합니다.
그리고 n’이 n과 같아지는 순간 종료합니다.

두번째 함수는 3의 성질을 이용해 n’이 진짜 소수인지 확인하는 함수입니다…
간단히 배열에 저장된…
root(n’)보다 작거나 같은 수로 나누어 봅니다…
이때 한번이라도 나누어 떨어지면 0을 리턴하고…
모두 나누어 떨어지지 않으면 1을 리턴합니다…

아침에… 대충 생각해본거라…
이상이 있는지 없는지는 잘 모르겠네요…

일단 이런식으로 구현하면… 중급은 되겠네요…
첫번째 함수에서… n이 소수일 확률이 없으면…
그냥 페스하고…
두번째 함수에서… n을 무작정 나눠보는것이 아니라…
root(n)까지만 나눠보니깐…
일반적인 방법보다는 훨 빠를테고…
배열로 소수를 저장하니깐요… 하하핫…

고급으로 풀고 싶긴 한데… 능력이 안되네요…

아직 언어를 잘 몰라요 ㅠ.ㅠ;;;

이번문제… 저한테는 너무 어렵네요 ^.^;;;


댓글 남기기