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

1과 자기 자신으로 밖에 나눠지지 않는 수 

 

0은 소수가 아니다.

1은소수가 아니다.

 

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

소수 (수론) - 위키백과, 우리 모두의 백과사전

https://namu.wiki/w/%EC%86%8C%EC%88%98(%EC%88%98%EB%A1%A0)

소수(수론) - 나무위키

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

해결 방법 

1. 길이가 n인 배열을 만들어 초기값을 true로 대입  

2. 반복문을 사용하여 2부터 n까지를 반복

3. 반복문 안에서 배열의 인덱스값이 true일경우 인덱스의 배수부터 인덱스 값만큼 증가 하며 n까지 반복문 실행 

4. 위 반복문에서 배열의 인덱스값을 false로 대입 

5. 배열의 인덱스 값이 true인경우만 소수가 됨 

 

 

using System;
using System.Collections.Generic;
 
namespace Application
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            //소수 구하기 (에라토스테네스의 체)
            var sol = new Solution();
            var result = sol.solution(20);
            Console.WriteLine("result: " + result);
 
        }
    }
 
    public class Solution
    {
        public int solution(int n)
        {
            int answer = 0;
            bool[] arr = new bool[n];
 
            for (int i = 2; i < n; i++) {
                arr[i] = true;
            }
 
            for (int i = 2; i < n; i++) {
                if (arr[i]) {
                    for (int j = i * i; j < n; j += i) {    //i의 배수는 소수가 아님 
                        arr[j] = false;
                    }
                }
            }
 
            for (int i = 0; i < arr.Length; i++) {
                if (arr[i]) {
                    Console.Write(i + " ");
                    answer += 1;
                }
            }
 
 
            return answer;
        }
    }
}