| [답변] 컴퓨터 프로그램 알고리즘? |
푸른하늘 |
컴퓨터로 소수를 찾는 알고리즘을 물어보시는 것 같네요. 맞죠? ^.^ 저도 무식하지만 답 비슷한 걸 해 드리죠. 특히 숫자가 20자리이면... 무지막지하게 크네요... 알고리즘으로 프로그래밍하는 건 즉석에서 좀 어려우니까(지금은 저녁먹으러 가야돼서...) 소수 찾는 법을 몇 개 가르쳐드릴테니 참고하세요.
1) 단순한 방법 : 2,3을 제외한 모든 소수는 6n+-1(6의 배수 플러스마이너스 1)의 꼴로 나타내어집니다. 그러니까 이런 수가 아니면 우선 제거하시고.
2) 조금 더 단순한 방법 : 그 수가 소수인지 아닌지 알아보려면 나누어 봐야 돼죠? 그런데 언제 그거 다 나눕니까? 좀 더 쉽게 하려면.
i) 2부터 그 수 하나 앞까지 나누는게 아니라 2부터 그 수의 제곱근까지만 나누어도 됩니다. 왜 그런지는 곰곰히 생각하면 쉽고.
ii) 2부터 그 수의 제곱근까지 모든 수로 나누어 볼 것 없이 그 범위 안에 있는 소수로 나누어보면 됩니다. 그 전까지의 소수를 배열에다 기억시키고, 거기서 범위에 알맞는 소수를 꺼내와서 나누어 보면 좀 더 빠르게 찾을 수 있겠군요. 원리는... 2로 나누어지지 않으면 4로도 나누어지지 않습니다. ^.^
원래 이런 건 제가 해 보고 알고리즘을 올려드려야 겠지만, 저도 학생이고, 시간이 없어서... 이렇게만 올립니다. 잘 읽어보시고 어떻게 프로그래밍해야 될 지 생각해 보세요. 그럼 전 이만...
cf) 메르센 소수를 이용하면 너무 쉽지만, 선생님께서 그걸 요구한 것 같지는 않으시네요. 메르센 소수를 쓰면 한방인데.
관리자주 : 메르센 소수를 써도 한방이 아닙니다.
|
| 작 성 일 : 2000년 03월 22일 |
첨부화일 : |
|
수열, 급수, 점화식, 순서도