[TIL] 119 [C#] 소수(Prime Number) 구하기 에라토스테네스의 체

---

소수구하기(Prime Number) 에라토스테네스의 체

공부

   알고리즘 연습하기
   클린코드 정리하기
   [ ] 디자인 코드 패턴 이해,정리하기. 책사기
   [ ] 자료구조 디자인패턴 강의 다시 듣기.

---

소수 구하기 (에라토스테네스의 체)

소수를 쉽고 빠르게 구할 수 있는 장점

• 일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거.
• 2를 제외한 2의 배수를 제거.
• 3을 제외한 3의 배수를 제거. ~ ~ ~ ~

// 모든 수를 소수로 가정
bool[] isPrime = new bool[N+1];
for (int i = 2; i <= N; i++)
{
    isPrime[i] = true;
}

// 에라토스테네스의 체
for (int i = 2; i * i <= N; i++)
{
    if (isPrime[i])
    {
        // I의 배수를 소수에서 제외
        for (int j = i * i; j <= N; j += i)
        {
            isPrime[j] = false;
        }
    }
}

for (int i = M; i < N+1; i++)
{
    if (isPrime[i])
    {
        Console.WriteLine(i);
    }
}

---

잡담, 일기?

이력서 정리, 자소서 작성, 면접준비중, 코테

---