백준 C++ 1929번 소수 구하기 ( 에라토스테네스의 체 )

 

 

오늘은 오랜만에 강남에 갑니다.

핸드폰 케이스도 사고

샤프도 사고

저녁도 먹고

그럴 예정입니다.

 

다녀오기 전에 문제를 풀어보겠습니다.

 

오늘은 쉽길 바라며..

아니

쉽게 풀 수 있길 바라며..🙏

---

 

문제가 엄청 쉬워 보이는데

정답률이 30 퍼도 안된다.

 

이유가 있을 텐데..

 

에라토스 어쩌고 체 가 생각나는데..

기억은 또 안나는...

 

 

일단..

막 짰는데..?

소수니까 1은 소수 아니고

2는 소수 3도 소수

.. 25는....?

.

..

아차차 25는 소수가 아닌데 5가 나온다..!!

 

에라이 퉤 체를 얼른 익혀야겠다.

맨날 까먹는다.

 

2026.02.25 - [C++을 시작해 봐요!/단계문제를 풀어보아요!] - 백준 C++ 1978번 소수 찾기 ( 에라토스테네스의 체 )

백준 C++ 1978번 소수 찾기 ( 에라토스테네스의 체 )

 

 

아... 벌써 두 달 전..

 

다시 공부해야 할 거 같다.

아니 왜 맨날 까먹냐!!!!!!!!!!!

 

진짜 진짜 기억하자

 

1.

0과 1은 소수가 아닙니다.

소수가 아니기 때문에

제외해줘야 합니다.

 

저는 제외를 true로 설정했습니다.

그래서 이렇게 합니다.

 

2.

2부터 시작합니다. 원하는 숫자까지

0과 1은 이미 설정했으니

2부터 시작합니다.

대신 m까지 숫자를 세야 하기 때문에 <= 해줘야 합니다.

 

그리고 중요한 것은 제곱이 중요한데,

16을 예시로 하면

1 16

2 8

4 4

8 2

16 1

4를 기점으로 앞 뒤가 똑같습니다. 그래서

i*i <= m을 해주면 더! 빠르게 문제를 구할 수 있습니다.

i <= m 도 되긴 합니다!!

3.

만약에 소수면, 한번 더 체에 걸린다.

한번 더 걸러줘야 합니다..

그때는 어떤 걸 걸러줘야 하나

3부터는 이제 배수는 다 걸러줘야 합니다.

4도 5도 6도.. 7도.. 등등..

그래서 i *2를 해줘서 또 끝까지 해준다.

 

중요한 것은 배수를 잘라내는 것이기 때문에

j += i 이렇게 해줘서

3+3 = 6

6+3 = 9

9+3 = 12

이렇게 진행된다.

이렇게 해서 배수면?

넌 소수가 아니다. 

 

처음에 i * i가 아니라 i * 2 여도 괜찮습니다.

근데 2는 이미 처음에 지워졌기 때문에 중복적인 계산이 될 뿐!

그래서 i*i가 더 효율적입니다.

기억 안 난다면..? i *2라도...ㅎ

 

 

 

그러면 이렇게 식이 나오게 됩니다.

---

 

아이 참 

풀었던걸 또푼 느낌..

아니 근데 에라이 퉤 체 왜 이리 머리에 안 들어올까요.

진짜 이틀마다 한 번씩 시험이라도 봐야 할까요....

후..

 

진짜 이제는 외울 겁니다.

나 진짜 안 외우면 안 된다.

나 사람 아니다.

나 진짜 외운다.