[c] 에라토스테네스의 체로 소수 찾는 프로그램

---

에라토스테네스의 체란?

대표적인 소수(Prime Number)를 판별하는 알고리즘이다.

 

 

 

주어진 수에서 2의 배수, 3의 배수, 5... 처럼 특정 숫자의 배수에 해당하는 숫자들을 먼저 지우고,

그렇게 채 처럼 걸러지고 남은 수들을 소수라고 합니다.

 

이는 대량의 소수를 한꺼번에 판별하고자 할 때 유용합니다.

 

---

 

에라토스테네스로 소수를 찾는 프로그램을 c언어로 구현하였습니다.

 

#include <stdio.h>
int main(){
  int num = 100;
  int count_prime = 0;

  int arr[100];

  for(int i=0; i<=num; i++){
    arr[i] = i; //자기 자신 인덱스로 초기화
  }
  
  for(int i=2; i<=num; i++){
    if(arr[i] != 0){
      for(int j=2*i; j<=num; j+=i){
        arr[j] =0; //i의 배수인 인덱스 값을 0으로 초기화
      }
    }
  }
  for(int i=2; i<=num; i++){
    if(arr[i]!=0){ //0이 아닌 값을 전부 출력
      printf("%d ", arr[i]);
      count_prime ++;
    }
  }
  printf("\n 소수의 개는 총 %d 개\n", count_prime);
  return 0;
}