[백준/C++] 1929번: 소수 구하기 (여러가지 소수 판별법)

제일 큰 수가 1,000,000으로 for문을 돌며 모든 수를 검사하면 시간초과가 난다. 2가지 방법으로 시간을 줄여보자. (+ endl 쓰면 모든 방법에서 시간초과 나니 '\n'로..)

 

1. 에라토스테네스의 체 방법

 

2부터 시작해서 해당 수를 제외한 해당 수의 배수들을 제거한다.

 

#include<iostream>
using namespace std;

#define size 1000001

int a[size] = { 0,1 };
int main() {

	int M, N;
	cin >> M >> N;

	for (int i = 2; i <= N; i++)
		for (int j = 2; i * j <= N; j++)
			a[i * j] = 1;

	for (int i = M; i <= N; i++)
		if (!a[i]) cout << i << '\n';


	return 0;
}

 

2. 소수와 제곱근

 

그 수의 제곱근까지로 범위를 제한해서 소수인지 판별해도 된다.

 

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int M, N;
	cin >> M >> N;

	int max;
	for (int i = M; i <= N; i++) {
		int flag = 0;
		max = sqrt(i);
		if (max == 1 && i != 1) cout << i << '\n'; //제곱근이 1인 2,3은 소수이니 출력
		else {
			for (int j = 2; j <= max; j++) {
				if (i % j == 0) break;
				if (j==max) cout << i << '\n';
			}
		}

	}

	return 0;
}

 

3. 부르트 포스 방법 (시간초과)

 

#include<iostream>
using namespace std;

bool IsPrime(int a) {
	if (a == 1) return false;
	for (int j = 2; j < a; j++) {
		if (a % j == 0) return false;
	}
	return true;
}

int main() {

	int M, N;
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		if (IsPrime(i)) cout << i << endl;
	}

	return 0;
}