백준 C++ 1929번 문제 - 소수 구하기

요약

소수 판별에 관한 문제이다. 일정 범위까지의 수까지 소수를 판별해내어 구할 수 있는 가를 묻는 문제이다. 소수 판별에 대한 공식을 외워두는게 필요한 문제다.

 

풀이

소수 판별을 위해 쓰이는 에라토스테네스의 체를 이용한다.

 

코드

#include <stdio.h>
#include <vector>
using namespace std;

void che(bool arr[], int size)
{
	arr[0] = true;
	arr[1] = true;
	
	for (int i = 2; i * i < size; i++){
		if (arr[i] == true)
			continue;
		for (int j = i * i; j < size; j += i){
			arr[j] = true;
		}
	}
}

int main()
{
	int M, N;
	scanf("%d %d", &M, &N);
	bool* b = new bool[N+1]();
	che(b, N+1);
	
	for (int i = M; i < N+1; i++)
	{
		if (b[i] == true)
			continue;
			
		printf("%d\n", i);
	}
}

결과