[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소수 찾기 (1978)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소수 찾기 (1978)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소수 찾기 (1978)

 

---

 

1978번: 소수 찾기

[ 문제 ]

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

[ 입력 ]

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

[ 출력 ]

주어진 수들 중 소수의 개수를 출력한다.

 

---

[ 코드 ]

#include<iostream>
using namespace std;
// 소수의 특징 : N이 소수가 되려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 안됨

int main() {
	int N; // 수의 개수
	cin >> N;

	int A; // 입력값
	int cnt = 0; // 소수의 개수

	while (N--)
	{
		bool check = false; // 검사

		cin >> A;
		if (A == 1) // 1은 소수가 아님
		{
			check = true;
		}
		else {
			for (int i = 2; i < A; i++) // A가 4이상은 되어야 실행 가능한 구문
			{
				if ((A % i) == 0) // 0으로 나누어떨어지는 값이 하나라도 있으면
				{
					check = true;
				}
			}
			if (check == false)
			{
				cnt++;
			}
		}
	}

	cout << cnt << '\n';

	return 0;
}

 

- 소수 : 약수가 1과 자기 자신밖에 없는 수

1) N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

 * N의 약수중에서 가장 큰 것은, N/2보다 작거나 같기 때문에. (따라서 앞쪽만 검사해줘도 됨)

2) N이 소수가 되려면, 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	int N;
	cin >> N;

	int cnt = 0;
	while (N--)
	{
		bool check = false; 

		int x;
		cin >> x;

		if (x == 1)
		{
			check = true;
		}
		else if (x > 1)
		{
			for (int i = 2; i * i <= x; i++)
			{
				if (x % i == 0)
				{
					check = true;
				}
			}
			if (check == false)
			{
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)