[백준 알고리즘 c++] 문제 17. 소수 구하기 에라토스테네스의 체 1929

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

내 풀이)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{

	//
	// 문제
	// 1.  M 이상 N이하의 소수를 출력하는 프로그램을 작성하기
	// 입력
	// 1. M과 N을 입력 받는다.
	int M = 0;
	int N = 0;
	scanf("%d", &M);
	scanf("%d", &N);
	
	// 처리
	// 1. M과 N사이를 반복문을 돌려 소수를 구한다.
	for (int i = M; i <= N; i++)
	{
		bool exist = true;
		for (int j = 2; j <= i; j++)
		{
			//1과 자기 자신이 아닌 다른수로 나눠지면 false
			if (i != j && i % j == 0)
			{
				exist = false;
				break;
			}
		}

		if (exist && i != 1) {
			printf("%d\n", i);
		}
	}
	

	return 0;
}

문제점 : 시간초과가 나길래 시간 복잡도를 살펴보니 80만 가량이 되었다. 다른방식이 도무지 떠오르지 않아 정답을 찾아보았다. 살펴보니 반복문 자리에 특수한 조작이 필요했다. 예를들어 i2 를 사용한다던지, sqrt함수를 사용하여 제곱을 한다던지, ij 로 시간 복잡도를 줄이는 방식이 있다. 이 방식을 에라토스테네스의 체라고 한다. 내 머리가 너무 나쁜가보다... 왜 생각을 못할까

정답)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int prime_number[1000010] = { 0 };

int main()
{

	//
	// 문제
	// 1.  M 이상 N이하의 소수를 출력하는 프로그램을 작성하기
	// 입력
	// 1. M과 N을 입력 받는다.
	int M = 0;
	int N = 0;
	scanf("%d %d", &M, &N);

	prime_number[1] = 1;

	// 처리
	//소수 배열 만들기 => 소수 일땐 true 로 담기게 한다.
	// 1-1. 소수 의 법칙을 지정한다.
	// 1-2. 소수는 1과 자기 자신 이외에 약수를 가지지 않는 수를 이야기 한다.
	//배수일때를 제외 하면된다.
	for (int i = 2; i <= N; i++)
	{
		for (int j = 2; i * j <= N; j++)
		{
			prime_number[i * j] = 1;
		}
	}

	for (int i = M; i <= N; i++)
	{
		if (prime_number[i] == 0)
		{
			printf("%d\n", i);
		}
	}



	return 0;
}