[C] 백준 2581번 : 소수

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int isPrimeNumber(int x);			//소수 판별 함수 선언
int main() {
	int N, M, sum = 0, x = 0;
	int Prime[1230] = { 0 };	//10000이하의 소수는 1229개
	scanf("%d%d", &M, &N);
	for (int i = M; i <= N; i++) {
		sum += isPrimeNumber(i);
		if (isPrimeNumber(i) > 0) {
			Prime[x] = isPrimeNumber(i); 	//최소값 판별을 위해
			x++;
		}
	}

	int min = Prime[0];
		if (sum == 0) printf("-1");		//소수가 없을 시 -1 출력
		else printf("%d\n%d", sum, min);
	}


int isPrimeNumber(int x) {
	int length;
	length = sqrt(x);
	if (length == sqrt(x)) return 0;		//1을 배제하자
	for (int i = 2; i <= length; i++) {
		if (x % i == 0) return 0;
	}
	return x;
}

문제에서 요구한 것은 크게 3가지였다.

1.주어진 범위 내에 소수를 판별하고

2.그 판별한 소수들의 합을 구해라.

3.그 판별한 소수들의 최소값을 구해라.

소수를 판별하는게 가장 우선시되어야한다.

그 중 가장 효율적인 방법인 에라토스테네스의 체를 이용할 것인데

 

에라토스테네스의 체는

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

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

자세한 이유는 아래 링크에 기술되어있다.

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

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

 

소수의 판별이 완료되었다면 소수들의 합을 출력해야했다.

굳이 따로 변수에 초기화해줄 필요없이 sum 변수에 더해줬다.

 

최소값을 구해주는 과정은 바로 수행할 수 없다고 판단하여

Prime배열을 선언해주었는데 Prime배열의 크기는

문제에 나와있는 N,M이 10000이하의 자연수라 하였기 때문에

10000은 1229개의 소수를 가지고 있어 1230으로 크기를 선언해주었다.

 

1978번 : 소수 찾기를 선행하여 풀어봤다면 큰 문제 없이 풀 수 있는 문제였다.