[C#] 백준 27465번 소수가 아닌 수

[ 문제 ]

이 대회의 운영진 중 한 명인 KSA 학생은 17시와 19시를 구별할 수 없다. 이는 당연하게도 17과 19가 모두 소수이기 때문일 것이다. 시간을 제대로 구별해서 KSA의 명예를 지키기 위해 정수 N을 입력받아서 소수가 아닌 N 이상의 정수를 아무거나 구해주자.

 

[ 코드 ]

using System;

int N = int.Parse(Console.ReadLine());

int nonPrime = FindNonPrime(N);
Console.Write(nonPrime);

bool IsPrime(int n)
{
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;

    int sqrtN = (int)Math.Sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int FindNonPrime(int n)
{
    while (true)
    {
        if (!IsPrime(n))
            return n;
        n++;
    }
}

 

[ 풀이 ]

- 주어진 수가 1보다 작거나 같으면 소수 X

- 2는 짝수 중 유일하게 소수

- 2로 나누었을때 나머지가 0이거나, 제곱근까지 i로 나눴을때 0이면 소수X, 어떤 수로도 나누어 떨어지지 않으면 소수O

 

문제에서 소수가 아닌 N이상의 값을 출력하라고 했으니 소수가 아니면 그냥 반환하고 소수면 +1하고 반환 해줬다.

 

[ 실행화면 ]

case: 소수가 아닌 수

case: 소수

---

문제링크: https://www.acmicpc.net/problem/27465

27465번: 소수가 아닌 수