백준 1929번 - 소수 구하기

tmi)2022년의 개강날이다. 3학년의 시작이다.

OT가 끝나서 시간이 좀 비어서 중도에서 코딩 한문제 풀고 올린다.

 

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

사고과정)

우선 처음엔 당연히 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 예외처리안해서 틀림 ㅠ