소수 찾기

https://www.acmicpc.net/problem/1978

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	149119	69720	55856	46.689%

문제

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

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다.

다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

출처

• 데이터를 추가한 사람: bclim9108, nova9128
• 문제의 오타를 찾은 사람: djm03178

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

---

소수의 정의

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다.

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

소수의 정의를 사용하여 M이라는 수가 있다면

M % 1에서 M까지 == 0 인 경우의 수가 2개라면 소수라는 뜻이다.

수가 크지 않고 테스트 케이스가 적어서 적용할 수 있다.

통과된 코드

#include <iostream>

using namespace std;

int N, temp, result;

int arr[101];

int main()
{
	cin >> N;
	// N만큼 입력을 받는다.
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= N; i++) {
		temp = 0;
		for (int j = 1; j <= arr[i]; j++) {
			// 자신을 1 ~ 자신까지 전부 나누어 본다.
			// 만약 나머지가 0이 되는 경우가 2라면 소수
			if (arr[i] % j == 0) { 
				temp++; 
			} 
		}

		// 결과가 2라면 1과 자신만 있다는 뜻으로 소수
		if (temp == 2 ) { result++; }
	}

	cout << result; // 결과 출력
	return 0;
}

아무생각없이 1을 소수라고 생각하고 예외 처리를 해주어서 틀렸다.

1은 소수가 아니다!!!!!!