백준 24029번 문제 '2021은 무엇이 특별할까?'

 

문제 풀러 GO, GO

24039번: 2021은 무엇이 특별할까?

 

 

백준 24029번 문제 '2021은 무엇이 특별할까?'

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main(int argc, char* argv[]) {
	int N;
	int res = 0;
	int prePrime = 0;
	scanf("%d", &N);
	int max = 10001;
	bool* noPrimeNum = (bool*)malloc(sizeof(bool) * max);
	for (int i = 0; i < max; i++)
	{
		noPrimeNum[i] = false;
	}
	noPrimeNum[0] = true; noPrimeNum[1] = true;

	for (int i = 2; i <= (max-1)/2; i++) {
		if (!noPrimeNum[i]) {//소수라면
			for (int j = i+i; j < max; j += i) {
				noPrimeNum[j] = true;
			}
			if (prePrime * i > N) {
				res = prePrime * i;
				break;
			}
			prePrime = i;
		}
	}

	printf("%d\n", res);
	return 0;
}

저의 코드입니다!

 

소수를 찾을때 에라토스테네스의 체를 이용해서 풀었어요.

아마도 (max-1)/2 부분은 (max-1)에 루트를 씌워서 해도 소수들이 잘 걸러질 거예요!

 

noPrimeNum[0]과 noPrimeNum[1]의 방으로 갈 일은 없겠지만 이 둘이 소수가 아니라는 의미로 true를 넣어줬어요.

 

이걸 한 번에 풀지는 못했는데요 ㅜ

예전에 풀다가 안돼서 냅뒀다가 오늘 한 번 풀어봤어요.

예전에 못 풀었던 이유는 1을 입력했을때의 처리를 잘못 해줬기 때문이었어요 ㅠ.

 

처음에 prePrime을 1로 세팅해줬었죠. 아무 생각 없이요 ㅎ.ㅎ..

그때는 저 변수의 영향을 생각하지 못 했던 것 같아요.

처음에 나오는 소수 2일때는 이전 소수가 없기 때문에 그냥 처음에는 0으로 만들어줘야 하는 것이었습니다!

 

제가 처음에 못 풀었긴 하지만 간단한 문제였네요!

문제를 조금 더 분석해보고 코드를 작성해야겠습니다!