에라토스테네스의 체

이번 C#을 배우면서 소수를 구하는 프로젝트에 대해 배웠는데

에라토스네테스의 체가 생각나서 정리해보려한다.

---

먼저 소수란 1과 자기 자신만을 약수로 가지는 자연수이다.

ex): 2,3,5,7,11 · · ·

 

일반적으로 소수를 구하려면 어떤 수 n이 주어졌을 때 

n까지의 모든 자연수로 나눠서 나머지를 계산하여 소수를 걸러낼 것이다.

 

에라토스테네스의 체 공식은 어떤수 n이 주어졌을 때

n까지의 수 중에서 {sqrt(n)이하의 수들의 n까지의}배수들을 제거해주면 소수만 남게되는 원리이다.

에라토스테네스의 체.gif

풀이법↓

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

//출처:https://ko.wikipedia.org/wiki/에라토스테네스의_체//

 

저번 C#풀이에서

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace B08_Prime
{
  class Program
  {
    static void Main(string[] args)
    {
      // (1) 어떤 숫자가 소수인지를 판단하는 프로그램
      //Console.Write("숫자하나를 입력하세요: ");
      //int x = int.Parse(Console.ReadLine());

      //int i;
      //for (i = 2; i < x; i++)
      //{
      //  if (x % i == 0) // 소수가 아님
      //    break;
      //}
      //if (i == x)
      //  Console.WriteLine("소수입니다.");
      //else
      //  Console.WriteLine("소수가 아닙니다");

      // (2) 1000까지 소수를 출력하고 몇개인지를 출력하는 프로그램
      int nPrime = 0;
      for (int x = 2; x<=1000; x++)
      {
        int i;
        for (i = 2; i < x; i++)
        {
          if (x % i == 0) // 소수가 아님
            break;
        }
        if (i == x)
        {
          Console.Write("{0}\t", x);
          nPrime++;
        }
      }
      Console.WriteLine();
      Console.WriteLine("소수의 갯수 = {0}", nPrime);
    }
  }
}

이 코드는 이중으로 순차탐색을 하여 소수를 뽑아내는 코드였다.

하지만 이 방법은 시간복잡도가 O(n^2)이기 때문에 많은 시간이 소요된다. 최악의경우

1000{2*0+(1000-1)*1}/2

=499500번을 계산해야한다.

 

하지만 체 공식을 사용하면 매우 빠르게 계산이 가능하다.

#include<stdio.h>
#include<math.h>

int main(void)

{
	int num;
	int cnt = 0;
	int arr[10000];
	scanf("%d", &num);

	for (int i = 2; i <= num; i++)
	{
		arr[i] = i;
	}

	for (int i = 2; i < sqrt(num); i++)
	{
		if (arr[i] == 0) continue;    // 0이면 건너뛰고 아니면 실행
		for (int j = 2 * i; j <= num; j += i)
		{
			arr[j] = 0;
		}
	}

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0) printf("%d ", arr[i]);
	}


}

1.배열arr에 1~num까지의 수를 차례대로 저장해준다.

2.최소 소수인 2부터 sqrt(num)까지의 루프를 생성해준다.  //num이 소수점을 포함하는 실수일 경우 올림계산해준다.

3.arr[i]==0일경우 아무일도 일어나지 않는다.

4.arr[i]!=0일경우 arr[j]=0으로 변경해준다.

   {j는 최소 4부터 시작하며 (가장 작은 소수의 2의 2배수인 4부터 계산함)i가 2일때 4->6->8 · · ·

    i=3일때 3->6->9 · · · 로 늘어난다.}

5.이에 해당하는 값을 전부 0으로 바꾸면 배열 arr안에는 0과 소수만 남게됨

6.출력해주면 끝

 

에라토스테네스의 체 공식의 빅오는  O(n loglog n)이므로 

1000*0.47 = 470

번으로 아주 간단하게 구할 수 있다.

 

조만간 C#코드를 짜봐야겠다