C# 소수 개수 구하기-1

이번 글에서는 N을 입력받고 1부터 N까지 소수 개수를 출력하는 프로그램을 만들어 보겠습니다.

 

먼저 소수는 1과 자기 자신으로만 딱 나눠 떨어진다는 특징을 가지고 있기 때문에

x가 소수인지 아닌지 알기 위해 2부터 x-1까지의 수로 x를 나눴을때

나머지들이 0이 아니라면 이 수는 소수라고 할수 있겠죠?

이를 함수로 구현해 보면 다음과 같습니다.

static bool isPrime(int x)
    {
        // 0과 1은 소수가 아니기 때문에 예외처리 해주겠습니다.
        if (x < 2) return false;

        //n이 2이상이라면 아래 코드를 실행합니다.
        for (int i = 2; i < x; i++)
        {
            // 만약 x/i가 나머지가 0이라면
            if (x % i == 0)
                // 소수가 아니므로 거짓을 반환합니다.
                return false;
        }
        // 만약 for문이 모두 실행됐으면 소수란 뜻이므로 참을 반환합니다.
        return true;
    }

 

다음은 그냥 이 함수를 써주기만 하면 됩니다.

using System;
class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (isPrime(i)) count++;
        }
        Console.WriteLine(count);
    }
    static bool isPrime(int x)
    {
        // 0과 1은 소수가 아니기 때문에 예외처리 해주겠습니다.
        if (x < 2) return false;

        //n이 2이상이라면 아래 코드를 실행합니다.
        for (int i = 2; i < x; i++)
       {
            // 만약 x/i의 나머지가 0이라면
            if (x % i == 0)
                // 소수가 아니므로 거짓을 반환합니다.
                return false;
        }
        // 만약 for문이 모두 실행됐으면 소수란 뜻이므로 참을 반환합니다.
        return true;
    }
}

수고하셨습니다.