[C언어] 추억의 소수 구하기

예전에 수학책에 나와 있는 공식들을 코딩화 하는 연습을 많이 했었네요. 그 추억을 떠올리면 공식 하나를 post으로 작성합니다.

1. 소수 구하기

소수란 약수로 1과 자기 자신의 수만 갖는 형태를 말합니다.

    t = 2;
    while(t<i)
    {
       if(i % t ==0) //나누어 떨어지는지 확인(소수 확인)
           break;
       else
           t++;
    }
    if (i==t) //임의의 i값과 비교 t값이 일치(소수)이면 결과 출력
    {
       printf("%d ",i);
    }

임의의 i가 소수인지 아닌지 확인 하기 위해서 t로 나누어 떨어지는지 if문으로 비교합니다. 이 과정을 t가 i가 될때까지 반복 비교하게 됩니다. 여기서 만약 t로 나누어 떨어지면 소수가 되지 못합니다. 그때 break문으로 while문을 빠져 나옵니다.

while문이 t가 i보다 작은 수로 빠져 나오면 나누어 떨어진 수가 있다는 의미가 되고 임임의 i수값을 출력되지 않습니다. 하지만 t가 i와 같다면 i는 소수가 되고 해당 i값은 printf문으로 결과를 출력하게 됩니다.

2. 코딩 실험

그러면 위 로직으로 임의의 소수를 구해보는 실험을 해보겠습니다.

문제 : 100까지의 소수를 모두 구하시오?

#include 
void main()
{
   int max = 100; //소수 체크 범위
   int i = 0;  //임의의 수
   int t = 0; //소수 비교 수

   for(i = 1; i<max; i++)
   {
      t = 2;
      while(t<i) 
      {
        if(i % t ==0) //소수 체크
           break;
        else
           t++;
      }
      if (i==t)
      {
       printf("%d ",i); //소수 결과 출력
      }
   }
   printf("\n");
}