정보처리기사 실기 알고리즘 정리 02

int main() {
 
  int input, i, j;
 
  scanf("%d", &input);
 
  i = input - 1;
  j = 2;
 
  while (1) {
 
    if (j <= i) {
 
      if (input % j == 0) {
        printf("소수 아님.");
        break;
      } else {
        j++;
      }
 
    } else {
      printf("소수.");
      break;
    }
  }
  return 0;
}

int main() {
 
  int input, i;
 
  scanf("%d", &input);
  i = 2;                    // 제수
 
  while (input % i != 0)    
    i++;
 
  if (input == i)           // 제수 == 피제수
    printf("소수");
  else
    printf("소수 아님");
 
  return 0;
}

#include<math.h>
 
int main() {
 
  int input, i;
 
  scanf("%d", &input);
  i = 2;                        // 제수
 
  while(1) {
 
    if (i <= sqrt(input)) {        // 제수가 제곱근보다 작은 동안에 나눠 떨어지면 소수아님
      if (input % i == 0) {
        printf("소수 아님.");
        break;
      } else {
        i++;
      }
    } else {                    // 위에서 안 나눠 떨어지고 제수가 제곱근보다 크면 소수
      printf("소수.");
      break;
    }
  }
  return 0;
}

int main() {
 
  int input, sum, i, j;
 
  scanf("%d", &input);       // 소수를 구할 숫자의 범위를 입력 받음.
 
  sum = 0;
  i = 2;                     // 소수인지 판별할 숫자가 저장될 변수
 
  while(1) {
 
    j = 2;                   // 제수
 
    while (i % j != 0)
      j++;
 
    if (i == j)              // 나눠 떨어졌는데 제수와 피제수가 같다면(소수)
      sum += i;     
 
    if (i < input)           // 입력받은 a 보다 작으면 피제수를 키워서 반복
      i++;  
    else {
      printf("%d", sum);
      break;
    } 
  }
  return 0;
}

int main() {
 
  int k, i, j, m;
  int a[99];
 
  k = 1;
  do {
 
    k++;
    a[k - 2] = k; 
 
  } while(k < 100); // 2~ 100까지 값을 배열에 할당
 
  i = -1, j = 0;    // 배열 a의 첨자 i는 i++을 수행한 후 0이 되도록 -1로 초기화
                    // j는 소수의 개수를 담을 변수
  while (1) {
 
    i++;
    if (i > 98) {       // a[98](=100)을 넘으면 출력
      printf("%d", j);  // 소수의 개수 출력
      break;
    }
 
    if (a[i] == 0) {    // 값이 0이란 의미는 소수가 아니란 뜻이므로.
      continue;
    }
 
    j++;                // 소수+1
    m = i;              // 소수를 구한 현재 배열의 위치 i를 그 소수에 대한 배수가 들어 있는 위치를 계산하기 위해 m에게 줌
 
    while (1) {
 
      m += a[i];        // 현재 배열의 위치(m)에 이번에 찾은 소수(a[i])를 더해주면 그 소수의 배수가 들어있는 위치가 계산됨.
 
      if (m > 99)       
        break;
      a[m] = 0;         // 소수의 배수가 들어있는 위치에 0을 기억시켜 소수가 아님을 표시
 
    }
  }
  return 0;
}

int main() {
 
  int a, b, big, small, mok, nmg, gcd, lcm;
 
  scanf("%d %d", &a, &b);
 
  if (a >= b) {       // 입력 받은 a, b 중 큰 수를 big에 작은 수를 samll에 할당
    big = a;
    small = b;
  } else {
    big = b;
    small = a;
  }
 
  while (1) {
    mok = big / small;
    nmg = big - mok * small;    // 나머지 = 큰수 - (몫*작은수)
 
    if (nmg == 0) {             // 나머지가 0 일 때,
      gcd = small;              // 작은수가 gcd(최대공약수)
      lcm = a * b / gcd;        // lcm(최소공배수)는 첫큰수*첫작은수/gcd
      printf("%d %d", gcd, lcm);
      break;
    }
 
    big = small;                // 나머지가 0이 아니면 작은수를 큰수로
    small = nmg;                // 나머지를 작은 수로해서 반복
  }
 
  return 0;
}

int main() {
 
  int input, mok, nmg, i;          
  int divisor[100];           // 약수를 저장할 배열
 
  scanf("%d", &input);        // 약수를 구할 숫자를 input에 입력받음.
  int c = 0, d = -1;          // c는 제수 d는 약수 배열 인덱스
 
  while (1) {
    
    c++;
 
    if (c <= input) {         // 입력받은 input까지 제수로 나눴을 때 나머지가 0인 약수를 구함
      mok = input / c;
      nmg = input - mok * c;
      if (nmg == 0) {
        d++;
        divisor[d] = c;
      }
    } else {
      printf("%d ", input);
      for (i = 0; i <= d; i++) {
        printf("%d ", divisor[i]);
      }
      break;
    }
  }
  return 0;
}

int main() {
 
  int n, pIndex, d, e, mok, nmg;
  int p[100];
 
  scanf("%d", &n);       // 정수 n을 입력받아서 소인수 구해 출력
 
  pIndex = -1;           // 소인수를 저장할 배열의 인덱스
  d = 2;                 // 제수
 
  while (1) {
    e = (int)sqrt(n);    // 입력 받은 값 n의 제곱근(e)을 구해 정수로 변환
  
    while (1) {
      if (d > e) {       // 제수가 n의 제곱근(e)보다 커지면 
        d = n;           // 피제수(n) 자체가 소인수
        break;
      }
 
      mok = n / d;
      nmg = n - mok*d;
 
      if (nmg == 0)       // 처음으로 나머지가 0이 되게 하는 수가 그 수의 소인수.
        break;
      else
        d++;              // d를 2부터 b의 제곱근(e)까지 증가 시키기 위해 1을 더함.
    }
 
    pIndex++;             // pIndex늘리고
    p[pIndex] = d;        // 소인수를 저장하는 배열p[]에 제수 저장
 
    if (n == d)           // 제수가 입력값과 같으면 소인수분해 과정을 모두 마친 것.
      break;
                          // 소인수를 구하고 분해과정이 모두 안끝났다면(n != d)
    n = mok;              // 그 때의 mok을 n로 하여 반복
  
  }
 
  for (int i = 0; i <= pIndex; i++) {    // 소인수 출력
    printf("%d ", p[i]);
  }
 
 
  return 0;
}

int main() {
 
  int decimal, decimal_copy, bIndex, mok, nmg, i;
  int b[10];
 
  scanf("%d", &decimal);
  decimal_copy = decimal;        // 원래 입력값을 나중에 출력하기 위해 복사
  // c언어는 배열이 0부터 시작, bIndex++를 수행하고 0이되도록 -1로 초기화.
  bIndex = -1; 
 
  do {
    bIndex++;
    mok = decimal / 2;
    nmg = decimal - mok*2;
 
    b[bIndex] = nmg;             // 2로 나눈 나머지를 b배열에 저장
    decimal = mok;               // 몫을 10진수로 하여 2로 못 나눌 떄까지 반복
  } while (mok != 0);
 
  printf("%d ", decimal_copy);   // 원래 입력값 출력
 
  // 배열의 위치가 0 부터 시작하기 때문에 
  // 첨자 i는 2진수가 저장된 마지막 위치인 bIndex부터 0이 될때까지 반복 수행
  for (i = bIndex; i >= 0; i—)  
    printf("%d", b[i]);
 
  return 0;
}

...
int k;
...  
  do {
    bIndex++;
    mok = decimal / 2;
    nmg = decimal - mok*2;
    b[9 - bIndex] = nmg;    // 배열의 뒤쪽에서부터 차례로 저장되도록 처리
    decimal = mok;
  } while (mok != 0);
 
  printf("%d ", decimal_copy);
  k = 9 - bIndex;          // 2진수가 들어 있는 첫 번째 위치를 계산.
       
  for (i = k; i < 10; i++)  
    printf("%d", b[i]);
...