[C#] 소수 찾기 : 1978번

이번 문제는 C# 으로 구현하였습니다!

문제

 

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

---

해석

 

소수가 되기 위해선 1과 자기자신으로만 나누어져야 한다.

바꿔말해, 2와 자기 자신 - 1 사이의 숫자로 나누었을 때, 나머지가 0 이 아니면 소수가 아니다.

따라서, 입력받은 수를 2부터 입력받은 수 까지 나누어 나머지가 생기면 소수가 아니라고 판별하고,

그 외의 경우만 소수로 갯수를 세면 된다.

 

하지만, 2부터 자기자신 - 1 까지 일일히 확인하는 것보다 계산 속도를 줄일 수 있는 방법이 존재한다.이는 다음 링크를 참고하면 알 수 있다.

 

[C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번 (tistory.com)

[C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번

---

풀이

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

namespace ConsoleApp1
{
    internal class Class1
    {
		static void Main()
		{
			int N; int count = 0; // 수의 갯수, 소수 갯수
			bool[] isPrime; // 소수 판별
			string[] input; // 입력 받을 공간(문자열)
			int[] arr; // 입력 받을 공간(정수형)

			N = int.Parse(Console.ReadLine()); // 갯수 입력
			arr = new int[N]; // 갯수 만큼 배열 생성
			isPrime = new bool[N];
			// ================== 입력 ==================== //
			input = Console.ReadLine().Split(' ');
			for (int i = 0; i < N; i++)
			{
				arr[i] = int.Parse(input[i]);
				isPrime[i] = true; // 초기화
				// ================== 1 은 제외 ==================== //
				if (arr[i] == 1)
				{
					isPrime[i] = false;
					continue;
				}
				// ======== 1 과 자기 자신 사이에서 나눠지면 ========== //
				for (int j = 2; j < arr[i]; j++)
				{
					if (arr[i] % j == 0)
					{
						isPrime[i] = false;
						break;
					}
				}
			}
			// ================== 소수 갯수 출력 ==================== //
			for (int i = 0; i < N; i++)
			{
				if (isPrime[i]) count++;
			}
			Console.Write(count);
		}
	}
}