[BOJ_step_09] 수학2 01 ~ 05

수학2

수학을 다루는 문제들을 해결해 보자.

소수 찾기(1978)

문제풀이

입력 받은 숫자를 2부터 a까지 나누어 나누어 떨어지고 그 몫이 1이 아니면 Cnt++하여 소수 개수를 증가시킨다.
위 과정을 받은 숫자 개수 만큼 반복하여 소수의 개수를 출력한다.

void solution_1978() {
    scanf("%d", &N);
	while (N--) {
		int a;
		bool chk = false;
		scanf("%d", &a);
		for (int i = 2; i < a; i++) {
			chk = a % i == 0 ? true : false;
			if (chk)break;
		}
		if (a != 1 && !chk)Cnt++;
	}
	printf("%d", Cnt);
}

소수(2581)

문제풀이

이 문제를 해결하기 위해서 에라토스테네스의 체를 이용한다.
1 ~ 최댓값 까지의 boolen형 배열이 있을 때, 2의 배수 부터 root(최댓값)의 배수까지 자기 자신이 아닌 즉, i x 1이 아닌 배수의 배열 인덱스에 대해 on/off를 계속하여 준다.
그 결과 1을 제외한 수 중 해당 인덱스 배열이 false이면 소수 이다.

위 과정을 거친 후 N ~ M사이의 모든 소수를 구하고 누적합을 구하고 그 소수들 중 최솟값을 구하여 출력한다.

int M, N, Sum, Min;
bool Num[10001];
void solution_2581() {
	scanf("%d %d", &M, &N);

	/* 에라토스테네스의 채 */
	Num[0] = true;
	Num[1] = true;
	for (int i = 2; i <= 10000; i++)
		for (int j = 2; j <= 100; j++)
			if (i*j <= 10000 && !Num[i*j])Num[i*j] = true;
	
	for (int i = M; i <= N; i++) {
		if (Min == 0 && !Num[i])Min = i;
		if (!Num[i])Sum += i;
	}
	if (Min == 0)printf("-1\n");
	else printf("%d\n%d\n", Sum, Min);
}
int main() {
	solution_2581();
	return 0;
}

소수 구하기(1929)

문제풀이

위 문제와 동일하다.

int M, N;
bool Num[1000001];
void solution_1929() {
	scanf("%d %d", &M, &N);
	Num[0] = true;
	Num[1] = true;
	int i = 2, j = 2;
	while (i*j <= 1000000) {
		for(int j=2; j*i<=1000000; j++)
			if (!Num[i*j])Num[i*j] = true;
		i++;
	}
	for (int i = M; i <= N; i++)
		if (!Num[i])printf("%d\n", i);
}
int main() {
	solution_1929();
	return 0;
}

베르트랑 공준(4948)

문제풀이

위 문제와 동일.

int N;
bool Num[246913];
void solution_4948() {
	Num[0] = true;
	Num[1] = true;
	int i = 2, j = 2;
	for (int i = 2; i <= 123456; i++)
		for (int j = 2; j*i <= 246912; j++)
			if (i*j <= 246912 && !Num[i*j])Num[i*j] = true;

	while (1) {
		scanf("%d", &N);
		int Cnt = 0;
		if (!N) break;
		for (int i = N+1; i <= 2 * N; i++)
			if (!Num[i])Cnt++;
		printf("%d\n", Cnt);
	}
}

골드바흐의 추측(9020)

문제풀이

에라토스테네스의 체를 이용하여 소수를 먼저 구하고 소수가 아닌 수 n를 2로 나누어 a=n/2, b=n/2 에서 a--와 b++를 진행하며 그 수가 소수가되는 첫번 째 순간의 두 수를 출력한다.

bool Num[10001];
int A, B;
void GoldBach(int a,int b) {
	A = a;
	B = b;
	if (!Num[A] && !Num[B])return;
	GoldBach(a - 1, b + 1);
}
void PrimeNum() {
	Num[0] = true;
	Num[1] = true;
	for (int i = 2; i <= 10000; i++)
		for (int j = 2; i*j <= 10000; j++)
			if (!Num[i*j])Num[i*j] = true;
}
void solution_9020() {
	int t;
	scanf("%d", &t);
	PrimeNum();
	while (t--) {
		int n;
		scanf("%d", &n);
		A = n / 2;
		B = n / 2;
		GoldBach(A, B);
		printf("%d %d\n", A, B);
	}
}