[C언어] 소수 출력 프로그램 (+ for문의 실행 순서 )

숫자를 입력받고, 그 숫자보다 작은 모든 소수를 출력하는 프로그램을 만들어보자.
소수란? [素數, Prime Number]
1과 자기 자신만으로 나누어지는 1보다 큰 양의 정수를 말한다. 예를들면‥ 2, 3, 5, 7, 11, 13, 17 …
소수인지 아닌지를 판정하려면?
자연수 N이 있다고 가정하자. N을 2부터 N-1까지 나눠봐서, 나머지가 0으로 떨어지는 값이 없으면 그 수는 소수이고, 있으면 합성수 즉, 소수가 아니다.
또 다른 판정법으로는 2≤P≤√N인 범위에 있는 모든 소수 P로 N을 나눠봐서, 나머지가 0으로 떨어지는 값이 없으면 소수이고, 있으면 소수가 아니다.

코드 (Code)

#include <stdio.h>

int main(void)
{
	int pri,cnt,i,num; // pri는 소수판정을 위해, cnt는 자연수를 위해, num은 범위를 위해 선언

	cnt=2; // cnt는 2이상의 자연수부터‥ (1은 소수가 아니다)
	printf("최대 몇까지의 소수를 출력하시겠습니까?: ");
	scanf("%d",&num); // 최대 출력값을 num으로 설정하기 위해 입력받음

	while(cnt<num)
	{
		pri=1; // pri는 소수판정을 위한 값, 기본값은 1
		for(i=2;i<cnt;i++) // i는 2부터 cnt값이 되기 전까지 증가시킴 (즉, 2≤i≤cnt-1)
		{
			if(cnt%i==0) // cnt가 i로 나눠 떨어지면
			{
				pri=0; // pri의 값을 0으로 변경, 소수가 아님을 뜻함
				break; // for문 탈출
			}
		}
		if(pri==1) // 16줄에 있는 if문을 만나지 않았다면 pri의 값은 1을 유지, 즉 소수임을 뜻함
		printf("%d ",cnt); // 해당 숫자를 출력
		cnt++; // cnt의 값을 1씩 증가, 최대 num이 되기전까지
	}
	printf("\n");

	return 0;
}

 

결과 (Result)

최대 몇까지의 소수를 출력하시겠습니까?: 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

팁 (Tip)

<for문의 실행 순서> 

 /* for문의 기본 형태 */
  for ( ⓐ초기화 ; ⓑ조건식 ; ⓒ증감식 )
  {
      ⓓ내용
  }
  ⓔ for문을 벗어남

 
  1. 우선 ⓐ초기화로 들어갑니다. 이곳에는 i=0, j=0등의 초기화 내용이 오게됩니다.
     조건식에 상관없이 무조건 실행하며, 단 한번만 실행됩니다.
  2. ⓐ를 거치면 바로 ⓑ조건식으로 넘어갑니다. ⓑ의 조건에 성립하면 for문이 내용으로 넘어가게
     되며(ⓓ), 조건이 성립하지 않으면 바로 탈출하여 for문을 벗어나게 됩니다.(ⓔ)
  3. ⓑ조건식이 성립하면, ⓓ내용으로 넘어가게 됩니다. { } 안에 있는 모든 내용을 위에서부터 아래로
     순차적으로 실행합니다.
  4. 내용안에 있는 식이 모두 마치게되면, ⓒ증감식으로 넘어갑니다.
  5. ⓒ증감식이 마치면, 다시 ⓑ조건식으로 넘어가고, 그 이후 진행은 2~4진행과 같습니다. 

 /* 위 코드를 이용한 예시 */
  7     cnt=2;
 11     while(cnt<num)
 12     {
 13         pri=1; 
 14         for(i=2;i<cnt;i++) 
 15         {
 16             if(cnt%i==0)
 17             {
 18                 pri=0; 
 19                 break; 
 20             }
 21         }
 22         if(pri==1) 
 23             printf("%d ",cnt); 
 24         cnt++; 
 25     }

 1. i는 2로 초기화. cnt의 값은 2고 i의 값도 2이므로 2<2가 성립되지 않아 탈출
 2. cnt의 값이 ++되어 3으로 되고, while문에 의해 for문이 재실행됨
 3. i는 2로 초기화. cnt의 값은 3이고 i의 값은 2이므로 2<3이 성립되어 for문 안으로 들어감
 4. { }안에 있는 내용을 실행하고, 증감식으로 돌아가 i++로 i의 값을 1증가시킴
 5. i와 cnt의 값이 둘다 3이므로, 3<3이 성립되지 않아 탈출 (이후 진행은 쭉 본과정과 같습니다)