[C] 백준 1978번 : 소수 찾기

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

1978번: 소수 찾기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
bool isPrimeNumber(int x);			//소수 판별 함수 선언
int main() {
	int N, count = 0;
	int t[100] = { 0 };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d",&t[i]);
		count += isPrimeNumber(t[i]);
	}
	printf("%d", count);
}
bool isPrimeNumber(int x) {
	int length;
	length = sqrt(x);
	if (length == sqrt(x)) return false;		//1을 배제하자
	for (int i = 2; i <= length; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

에라토스테네스의 체를 이용하여 문제를 풀었습니다.

N개의 수가 입력받게 되는 즉시 소수를 판별하는 함수를 거쳐 true 혹은 false 즉 bool타입으로 return됩니다.

true는 1로 해석되기 때문에 만약 소수라면 count 변수가 1씩 증가하게 될 것입니다.

 

이 때,1은 예외로 판별과정을 위해 반복문을 거칠 필요 없이 false로 return되게 하였습니다.

 

에라토스테네스의 체는

어떠한 숫자가 주어졌을 때 그 숫자의 제곱근 이하의 범위까지만 약수가 존재하는지 판별하면

그 숫자가 소수인지 아닌지 알 수 있게 해줍니다.

 

자세한 이유는 아래 링크에 기술하였습니다.

https://developer-dz.tistory.com/5

[C] 소수 구하기 / 에라토스테네스의 체 / 소수 구하기 최적화 / 1000개의 소수 구하기 / 범위 내의