정보처리기능사 실기 기출문제 유형#2 - 소수 알고리즘

Pretty little ponies yes that is what i like :3

정보처리기능사 실기 기출문제 유형#2 - 소수 알고리즘 소수 판별등.

1. 소수란?

- 소수는 자신과 1로만 나누어떨어지는 특수한 수입니다.

- 다른말로 약수가 자기자신과 1밖에 없는 수를 의미하죠.

- 예를 들면 1 2 3 5 7 11 13 같은것들이 있습니다.

2. 소수 알고리즘 :: 소수 구하는 방법

- 입력 받은 수 N, 검사용 변수 i

- i 는 2부터 시작 N-1 까지 +1씩 증가.

- N MOD i 값이 0인게 하나도 없을경우 입력받은 수 N는 소수. 

* 소수구하기의 핵심은 MOD 결과값이 0이여야 한다는것.

3. 제곱근을 이용한 소수구하기 알고리즘

- 제곱근을 구하는 함수는 SQR() 입니다.

- 어떤수가 소수인지 알아볼때, i를 굳이 N-1까지 전수검사하지말고 해당수의 "제곱근(자연수)"까지만

검사해도 됩니다. (불필요한 연산을 줄이는 효과가 있음)

- 예를들어 555이 소수인지 알아볼때 SQR(555) = 23.XXX, 23까지 만 검사해도 소수인지 아닌지의 결과는

산출됩니다.

4. MOD없이 소수인지 알아보는 특이한 방법 [kinda hard]

- MOD라는 나머지 구해주는 특수연산없이 "소수의 배수는 소수가 아니다"라는 성질과 배열을 이용해서

소수의 소수를 지워내서 소수인지를 판별할 수 있습니다.

2~1000까지의 수 중 소수의 개수는? 

A(999) = 2~1000까지의 수가 차례로 보관된 배열.

i = 0

Point1

i = i + 1

만약 A(i) = 0 이면 Point1로 아니면 이하를 실행하시오. // MOD연산 대신 여기서는 A(i) = 0 이 아니면 소수라고 판단하게 됩니다. 기묘하죠? 음, 2에서부터 1씩 늘려가며 소수를 찾고 소수의 배수를 지우는 아래과정을 참조하세요!

CNT = CNT + 1

만약 i = 999 이면 CNT를 출력하고 종료 아니면 이하를 실행하시오.

Point2

M = i

M = M + A(i) //소수의 배수의 자리를 구현

A(M) = 0 //핵심개념 : "소수의 배수"가 들어있는 배열의 자리에 0을 놓아서 삭제함.

M < 999 이면 Point2 으로 아니면 Point1로 가시오.