[BaekJoon 1929][⚪3] 소수 구하기
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (소수 판별)
- 알고리즘
Mathematics,Prime Number
- 설명
소수를 하나씩 판별하는 방식의 풀이이다.
흔하게 볼 수 있는 소수 판별을 해주는 함수를 따로 만들어서 매번 그 함수를 호출하는 방식으로 푸는 방식이다. '0', '1', '2' 같은 기본적인 숫자는 미리 판별하고 'sqrt(N)'까지 루프를 돌며 '홀수'만 따로 판별해주는데, 아주 유명하고 많이 쓰이는 방식이다.
소수 판별 함수 내부에서 sqrt(N)까지 반복문을 도므로 전체 시간 복잡도는 O(N√N)이다.
- 코드
내 풀이 코드
#include <iostream>
using namespace std;
bool IsPrime(int iInput);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iM{}, iN{};
cin >> iM >> iN;
if(iN < 2)
{
return 0;
}
for(int i = iM; i <= iN; ++i)
{
if(IsPrime(i))
{
cout << i << '\n';
}
}
return 0;
}
// 입력값의 소수 판별 함수
bool IsPrime(int iInput)
{
if(iInput <= 1)
{
return false;
}
if(iInput == 2)
{
return true;
}
if(iInput % 2 == 0)
{
return false;
}
// 3부터 시작해서 2씩 늘려가며 홀수만 판별
// sqrt(iInput) 까지만 검사하면 되므로 i * i을 조건식으로 넣음
for(int i = 3; i * i <= iInput; i += 2)
{
if(iInput % i == 0)
{
return false;
}
}
return true;
}
2. 추가 풀이 1 (에라토스테네스의 체)
- 알고리즘
Mathematics,Prime Number,Sieve of Eratosthenes
- 설명
에라토스테네스의 체 알고리즘을 사용하는 전형적인 소수 판별 방식이다.
상술한대로 전형적인 에라토스테네스의 체 알고리즘 방식이다.
주의할 점은 오버플로우를 방지하기 위해 루프문에 1LL를 사용해주는 것과 vector<bool> 대신 vector<char>를 사용해주는 것이다. vector<bool>은 '메모리 절약'을 위해 내부적으로 '비트마스킹' 방식으로 따로 구현되어 있기 때문에, 일반적인 'vector'의 원리와 달라져서 뜻 밖의 로직 오류를 일으킬 수 있기 때문이다.
에라토스테네스의 체의 시간 복잡도가 곧 전체 시간 복잡도이므로 O(N log log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iM{}, iN{};
cin >> iM >> iN;
if(iN < 2)
{
return 0;
}
// vector<bool>보다 안전한 vector<char> 선택
vector<char> vecNPrime(iN + 1, false);
vecNPrime[0] = vecNPrime[1] = true;
// 전형적인 에라토스테네스의 체
// 오버플로우 방지용 1LL 잊지 말 것!
for(int i = 2; 1LL * i * i <= iN; ++i)
{
if(vecNPrime[i])
{
continue;
}
for(long long j = 1LL * i * i; j <= iN; j += i)
{
vecNPrime[j] = true;
}
}
for(int i = iM; i <= iN; ++i)
{
if(!vecNPrime[i])
{
cout << i << '\n';
}
}
return 0;
}
3. 추가 풀이 2 (에라토스테네스의 체 변형)
- 알고리즘
Mathematics,Prime Number,Sieve of Eratosthenes
- 설명
에라토스테네스의 체 + 홀수만 판별 방식의 변형 버전이다.
위의 두 번째 풀이에서 '짝수'는 볼 것도 없이 소수가 아니므로, '홀수'만 따로 판별하는 방식으로 변형하는 방식이다. 이를 위해 vector의 공간 할당도 반절로 줄이고, 로직도 살짝 달라지는 것에 주목하면, 생각보다 쉽게 변형 가능하다.
거기에 추가적으로 위의 두 풀이와 다르게 string을 이용한 출력 최적화를 조금 곁들여 봤다.
위와 같이 O(N log log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iM{}, iN{};
cin >> iM >> iN;
if(iN < 2)
{
return 0;
}
// 홀수만 판별할 거라서 반절로 나눔
vector<char> vecNPrime(iN / 2 + 1, false);
vecNPrime[0] = true;
// 에라토스테네스의 체의 홀수 판별 변형 버전
for(int i = 3; 1LL * i * i <= iN; i += 2)
{
if(vecNPrime[i / 2])
{
continue;
}
// 여기서도 i를 더하는게 아니라 (i * 2)를 더해줘야함
// (홀수 + 홀수)는 짝수이기 때문에 피하기 위해
for(long long j = 1LL * i * i; j <= iN; j += i * 2)
{
vecNPrime[j / 2] = true;
}
}
// 출력 최적화 (한번에 출력)
string strOut{};
strOut.reserve(1000000);
if(iM <= 2 && iN >= 2)
{
strOut += "2\n";
}
if(iM % 2 == 0)
{
++iM;
}
for(int i = iM; i <= iN; i += 2)
{
if(!vecNPrime[i / 2])
{
strOut += to_string(i);
strOut += '\n';
}
}
cout << strOut;
return 0;
}
💭 후기
소수 판별 문제는 자주 나오면서도, 생각보다 쓸 수 있는 알고리즘도 많고 상황에 따라 성능이 확확 바뀔 수 있다는 것이 매력적인 것 같다. 세 번째 풀이의 홀수 판별 변형 버전처럼, 조금만 생각을 유연하게 해서 최적화를 생각하는 것도 좋은 것 같다. 참고로 실행 시간의 차이는 다음과 같다.
- 첫 번째 풀이 :
12ms - 두 번째 풀이 :
8ms - 세 번째 풀이 :
4ms
확실히 최적화의 차이는 있다. (참고로 안타깝게도 출력 최적화는 별 효과 없었다.. 그대로 4ms!)
Comments