1929번 소수 구하기 with C++

문제

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

1929번: 소수 구하기

 

해결한 방법

1978번 응용

#include <iostream>
#define MAX 1000001
using namespace std;

bool is_prime(int a) {
	if (a == 1)
		return false;

	for (int i = 2; i*i <= a; i++){
		if (a % i == 0)
			return false;
	}
	return true;
}

int is_prime_li[MAX];

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++){
		if (is_prime(i))
			cout << i << "\n";
	}

	return 0;
}

 

배열 이용

1. 배열의 인덱스를 찾는 찾는 수로 두고 합성수를 찾아내서 1로 바꿔주려고 합니다.
2. 배열에 2부터 n의 제곱근까지의 배수(최소 2배이상)들을 인덱스로 가지는 값들을 1로 바꿔줍니다.
3. m부터 n까지 배열의 값이 0인 인덱스만 찾아서 인덱스값을 출력해 줍니다.

#include <iostream>
#define MAX 1000001
using namespace std;

int is_prime_li[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int m, n;
	cin >> m >> n;

	int i;
	int check;
	for (i = 2; i * i <= n; i++) {
		check = i;
		if (!is_prime_li[check]) {
			while (check <= n) {
				check += i;
				is_prime_li[check] = 1;	// 소수가 아닌 수 1로 체크
			}
		}
	}

	is_prime_li[1] = 1;
	for (i = m; i <= n; i++) {
		if (!is_prime_li[i])
			cout << i << "\n";
	}

	return 0;
}