[C언어] 열혈강의 C프로그래밍(윤성우 저) 도전! 프로그래밍 ONE. 도전5

도전5. 10개의 소수(Prime Number)를 출력하는 프로그램을 작성해 보자. 정수 n이 1과 n으로 밖에 나눠지지 않는다면 이는 소수에 해당합니다. 따라서 3은 소수이다. 그러나 4는 소수가 아니다. 1, 2, 4 로 나눠지기 때문이다.

 

네.. 소수를 구하는 것입니다. 

현재 소수를 구하는 일반해는 없습니다. 

지금도 수많은 수학자를이 소수를 구하는 일반해를 구하기 위해 자신의 인생을 바치고 있습니다. 

우리는 계산이 매우 빠른 컴퓨터를 이용해서, 약간의 노가다성 알고리즘을 짤것입니다. 

(물론 노가다는 컴퓨터가 하는것입니다.) 

 

알고리즘입니다. 

n을 2부터 1씩 증가시키면서, n이 소수인지 아닌지 검사를 하는데,

i를 2부터 n까지 증가시키면서 계속 나누면서, 나머지가 0이 되면 검사를 중지하고 n을 1증가시켜 검사

i가 n이 될때까지 나머지가 0이 안되면(즉 어떤수로도 나눠 떨어지지 않으면)

n은 곧 소수입니다. 

 

의사코드 

 

n은 소수인지 아닌지 검사하는 숫자이며 

i는 그 검사를 도와주는 숫자입니다. 

for(n이 2부터 ; 1씩 증가 ; 소수를 10개 찾을때까지) 

{ 

  for(i는 2부터 ; 1씩 증가 ; n까지) 

  { 

     if(i가 n과 같아지면) 

      n은 소수이므로 n을 출력 

      소수 갯수 1 증가 

     if(n을 i로 나눈 나머지가 0이면, 즉 n이 i로 나눠 떨어지면) 

      반복문 탈출 (n이 소수인지 검사하는 과정을 중지) 

   } 

 } 

 

실제 코드 

딱히 설명드릴 내용은 없습니다.. 위에서 설명한 알고리즘과 의사코드를 이해했으면, 

충분히 이해가능하실것입니다. 

 

주석을 읽어보시기 바랍니다. 

 

실행결과. 

추가로, 카운터 변수를 따로 선언했기 때문에 추후에 

소수 갯수를 입력받는 기능을 확장한다고 하더라도 

크게 어려움 없으실 것입니다.(첫번째 포문 안에 숫자 10대신 입력값을 넣으면 됩니다.) 

 

이상입니다.