코딩테스트 입문 - 합성수 찾기 ( 이중 포문, 에라토스테네스의 체 )

 

조금 긴 연휴 사이에 월요일이군요!

저는 어린이날에는 알바를 갑니다.

그래서 오늘 문제를 열심히 풀어야 하지요.

 

오늘은

이름부터 어려운

문제도 어려웠던 문제를 풀려고 합니다.

 

함께 보시죠

 

---

 

합성수입니다.

 

합성수는 약수가 3개 이상인 수입니다.

그럼 여기서 문제!

소수랑 반대일까요?

 

완전히 답이 yes는 아닙니다.

예외가 있기 때문이죠.

 

숫자 1입니다.

이 친구는 소수도 아니고 합성수도 아니기 때문에

유일한 친구지요.

 

그래서 반대라고는 말 못 한다는 것...!

 

그러면 1 빼고 에라토스 어쩌고 체..

로 풀면 될 거 같은데

ㅋㅋ

나는 또 까먹었나 보다.

그래도 이번에는 고민해서 풀어보려고 한다.

 

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

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

 

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

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

 

 

1. 0과 1 제외해 주기

2. 배수.. 빼기

 

...

음

맞는데 기억이 잘 안 나네

 

심지어 제외해줘야 하는 건데

음

 

인지씨전에 내가 썼던 블로그에 정보를 얻어보기로 했다.

 

아!!!

배열을 하나 만들어서

거기에 bool값을 했던 거 같다.

 

오케이!

 

근데 이번에는 sosu를 구하는 거를 반대로 해줘 야하니까..

모든 값이 true로 시작해야 하는 건가?

점점 머릿속이 복잡해지는 순간...

 

벡터로 한번 풀어보려고 한다.

 

사실 배열의 경우 true 해주려면

for문 써야 해서

그냥 벡터로 풀려고 한 거다 데헷

 

༼ つ ◕_◕ ༽つ

 

벡터로 값 초기화하려면

괄호! 를 써야 한다.

vector <bool> sosu(101, true);

 

이렇게 해주면 소수 벡터들이 다 true가 된다.

더 나아가,

저기 101일에

n+1로 해주면 더 현명한 식이 된다!!!!

 

 

 

원래 소수를 구하는 에라토스테네스체는

모두 true로 시작하고

0이랑 1은 소수가 아니니 false 해주고

그리고 배수 찾으면서

소수가 아닌 애들을 다 false 해줬다.

 

근데 지금은 합성수를 구하는 거다.

 

 

즉 소수가 아닌 false를 구하는 거니까 식은 동일하다.

 

대신 false들의 카운트를 해주는 거니까

굳이 1과 0을 false 해줄 필요가 없다 어차피 제외되었으니까!!

 

그리고

애초에 1,2,3은 합성수가 아니니까 4부터 시작해서

크게 문제 되지도 않는다.

 

for문으로 i는 2부터 i*i <= n까지 중에

만약에 일단 모두를 true로 했으니

if ( 소수 ) 중에

또 다른 for문으로  j = i * i,  i j <= n까지 i += j;

얘네는 소수가 아닌 애들이니까 false 해준다.

 

그리고 for문으로 4부터 끝까지 false만 count 해주면 끝!

 

 

자잔

---

이렇게 합성수를 구해보았습니다.

치.. 어려웠는데 3점이라니

 

합성수..

소수 아닌 친구

 

소수 또 에라토스테네스를 맛봤습니다.

벌써 3번째인데..

여전히 틀리는 중

다음에 진짜 진짜 외운다고요!!

 

 

다른 사람들 한 100명 정도가 푼 식이 있었다.

 

합성수라 4부터 시작하고,

 

합성수란 약수가 3개 이상이라는

중요한 문구를 위에 적었는데

만약에 나눠지면 cnt++ 해주고

그게 3보다 크면? 결국 합성수니까 ++ 해주는..

아주 단순한 브루트포스로 풀었다.

.. 이렇게 풀이가 단순해서 3점이었나..

싶었다.

하지만 소수 그리고 합성수도 같이 공부해서

 

두 개 다 공부한 걸로 치자!!