Prime Number Algorithm

정의에 의한 알고리즘

 

(1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수)

 

1.   정수 N을 입력받는다.

2.   정수 I에 2를 대입한다.

        2.1   N이 i로 나누어 떨어지는가?

                2.1.1   나누어 떨어지면 소수가 아니다. 끝.

        2.2   i를 하나 증가시킨다.

        2.3   i가 N보다 작은가?

                2.3.1   작으면 2.1로 돌아간다.

3.   정수 N은 소수이다. 끝.

 

 

개선된 알고리즘

 

 소수의 정의대로 작성한 위의 알고리즘도 개선의 여지는 있다.

 

소수를 판별하는 방법자체를 개선하는 것은 아니고, 소수 판별을 위해 N에 나누는 i의 범위를 좁혀보자는 것이다.

 

 13이라는 숫자를 예를 들어보자. 13이라는 숫자가 소수인지 아닌지를 판별하기 위해 굳이 2부터 12까지의

 

숫자로 나누어 볼 필요가 있을까? 잘 생각해보면 2부터 13의 제곱근까지의 정수로만 나누어도 된다는 것을 알 수 있다.

 

 12라는 숫자를 예를 들어본다면 12는 2*6, 3*4, 4*3, 6*2 라는 조합이 생긴다.

 

여기서 앞쪽의 두 조합과 뒷쪽의 두 조합은 서로 대칭되는 모양임을 알 수 있다. 그래서 13이라는 숫자는

 

13의 제곱근까지만 나누어 보면 되는 것이다.

 

 이 사실을 이용하여 주어진 N에 대해 2부터 sqrt(N)까지의 숫자로만 나누어서 소수를 판별하는 함수를 작성해보자.

 

Hint)

#include<math.h>

sqrt()     -----실수형의 데이터를 인자로 받아서 실수형의 리턴값(제곱근)을 내놓는 함수