백준 문제풀이/실버3
백준 1929번 - 소수 구하기
void_melody
2022. 3. 2. 15:57
tmi)2022년의 개강날이다. 3학년의 시작이다.
OT가 끝나서 시간이 좀 비어서 중도에서 코딩 한문제 풀고 올린다.
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
사고과정)
우선 처음엔 당연히 M~N까지 2부터 M까지 쭈우욱 돌려보려했다.
하지만 이럴 경우 반복문이 두 개 이므로 O(N^2)이다.
저번에 소수 관련해서 포스팅을 올릴 때 , 에르테스토노스의 체? 라는 방법을 공지했다.
1 2 4 8 16이 16의 약수인데 어차피 16의 제곱근인 2 4로 나뉘어지는 거면 자연스레 8과 16도 나뉘어지는 것이므로
굳이 연산을 할 필요가 없다는 것이 핵심이었다.
그렇기에, 그냥 내가 구하고자 하는 수의 제곱근까지만 연산해서 나눠주면 어떨까하는 생각을 하였다.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int M, N;
cin >> M >> N;
for (int i = M; i <= N; i++)
{
int temp = sqrt(i);
bool flag = false;
if (i == 1)
continue;
if (temp == 1 && i != 1) // 2 or 3
{
cout << i << '\n';
continue;
}
if (i % 2 != 0)
{
for (int j = 2; j <= temp; j++)
{
if (i % j == 0)
{
flag = true;
break;
}
}
if (!flag)
cout << i << '\n';
}
}
return 0;
}
1,2,3이 특수 경우라서 조건문으로 예외처리해주었다.
처음에 1,2,3 예외처리안해서 틀림 ㅠ