소수 찾기 알고리즘 [C++], [BJ]1929 소수 구하기

소수란 약수가 1과 자기 자신밖에 없는 수를 의미한다.
그렇기에 소수 판정은 2부터 n-1까지의 숫자로 나누어 보면 되는데, 너무 많다...

따라서 흔히 두가지 방법이 주로 쓰이는데, 2 ~ √n 까지의 정수를 나누어 봄으로 알 수 있다.

√n까지 나누면서 확인

예를 들어 45의 경우 3,5,9,15를 약수로 가지는 데 15의 경우 이미 앞서 나온 3과 15의 곱이 45이기 때문에 앞서 나온 수에서 이미 체크가 가능하다. n^2인 49를 예를 들어보면 1~√49=7까지 확인해보면 된다.

<코드>

#include <iostream>
using namespace std;

bool is_prime(int n) {
	if (n < 2) return false;
	for (int i=2; i*i<=n; i++) {
		if (n % i == 0) return false;
	}
	return true; // 소수
}

다른 방법으로는 에라토스테네스의 체를 이용한 소수를 구하는 방법이 있는데

에라토스테네스의 체

1~n까지의 숫자를 쭉 써놓고, 2의 배수를 전부 지우고, 3의 배수를 전부 지우고.. 이런 식으로 해나가면서 1~n사이의 소수를 찾는 방법이다.

코드에서는 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

<코드>

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

vector<int> eratosthenes(int n) {
//먼저 배열을 정렬하고 이후 vector에 소수를 담는다.
	bool ary[n];
	for (int i = 0; i <= n; i++) ary[i] = false;
	ary[0] = ary[1] = true; // 0과 1은 소수가 아님

	vector<int> prime; 
	for (int i = 2; i <= n; i++) {
		if (ary[i]) continue; // 소수가 아니면 continue
		prime.push_back(i); // 소수라면 vector에 담는다.
		// i보다 큰(그래서 2번째인 i*2부터 시작) i의 배수를 제외
		for (int j=i*2; j<=n; j+=i) ary[j] = true; 
	}
	return prime;
}

int main() {
	int a;
    cin>>a;
	vector<int> prime = eratosthenes(a);
	for(auto x : prime) cout<<x<<' ';
}

100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

넓은 범위에서 소수 찾기가 필요한 경우 후자가 처리속도에서 우세를 보여 자주 사용한다.

BJ 1929

https://www.acmicpc.net/problem/1929
[소수 구하기]

<코드>

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

int arr[1000001]; //전역 변수는 0으로 자동초기화

void checkprime_print(int m, int n)
{
	//소수가 아니면 1
	arr[0] = 1;
	arr[1] = 1;

	for(int i = 2; i <= int(sqrt(n)); i++) { 
		for(int j = 2*i; j <= n; j += i) {
			if(arr[j] == 0) {
				arr[j] = 1; 
			}
		}
	}
	for(int i = m; i <= n; i++) {
		if(arr[i] == 0) printf("%d\n", i);
	}
}

int main()
{
	int m, n;
	scanf("%d %d", &m, &n);

	checkprime_print(m, n);

	return 0;
}

최대한 조금 더 빠른 방법들을 다 동원한 코드이다. sqrt를 이용하였을때와 그냥 i<=n 까지 했을 때도 시간이 꽤나 차이나는 편이다.