[C언어] 소수 (Prime Number)

소개

C언어를 이용하여 1부터 M까지의 자연수 중 소수를 판별하여 화면에 출력하는 알고리즘을 만들고, M값이 커질수록 수행시간이 얼마나 증가하는지를 관찰한다. 본 리포트는 한글로 작성되었으며, 해당하는 알고리즘과 소스 코드가 모두 첨부되어있다.

목차

1. n개의 자연수가 있을 때, 1에서 n까지 숫자로 나누어서 떨어지는지 검사하여 나누어떨어지는 수가 몇 개 있는지 검사하여 소수를 구하시오.
2. 소수를 구하는 새로운 알고리즘을 제안하고 1의 과정을 반복한 후, 1번의 결과와 비교하시오.

본문내용

1. n개의 자연수가 있을 때, 1에서 n까지 숫자로 나누어서 떨어지는지 검사하여 나누어떨어지는 수가 몇 개 있는지 검사하여 소수를 구하시오.

[Definition]
소수 : 1과 자기 자신만을 양의 약수로 갖는 수

가장 기본적인 소수의 정의를 이용하여, 1부터 해당 숫자를 차례로 나누어보면서 나누어 떨어지는 수가 몇 개 있는지를 통해 (나누어 떨어지는 수가 3개 이상일 경우 소수가 아니므로 버림) 소수를 구하는 코드를 다음과 같이 만들어 보았다.

먼저 해당하는 숫자가 소수인지 아닌지를 확인하는 c, 소수의 개수를 구하고자 하는 (처음에 입력받는) 범위 m, 그리고 판별된 소수의 개수를 세는 n이라는 변수를 정의하였다. 1부터 m까지의 숫자를 2 이상의 자연수로 하나하나 나누어가면서 나머지가 0이 될 경우 (나누어 떨어질 경우) c를 1씩 증가시킨다.

검사가 끝난 후 c가 1이 되는 숫자만 출력시켰는데, 1은 모든 숫자를 나누어서 나누어 떨어지므로 검사를 하지 않았고, 따라서 1을 제외한 나머지 숫자로 나누었을 때 카운트가 하나 (c=1)이라는 것은 1 외에 나누어 떨어지는 숫자가 하나밖에 없다는 말이므로 소수의 정의와 일치한다.
다음은 위의 코드를 컴파일 후 m=500일 때 실행시킨 결과이다.

다음은 m=40000, m=50000, m=90000일 때 소수의 개수만 출력하는 코드이다. 위의 코드를 대부분 이용했으나 개수를 출력하는 부분은 삭제하고, 예제 코드로 첨부된 수행시간 출력 코드에 이를 포함시켜 시간을 측정해 보았다. 수행 횟수는 10회로 측정하였다.

1) m=40000일 때

2) m=60000일 때

3) m=90000일 때

수행 결과 m값이 증가할수록 결과값을 출력하는데 걸리는 시간은 기하급수적으로 증가한다. 이를 통해 위의 코드가 결과 도출에는 아무런 문제가 없지만 코드 수행에 걸리는 시간을 고려해볼 때 매우 비효율적인 알고리즘을 이용하여 짜여진 코드임을 알았다.

참고자료

· 없음