GCD

https://www.acmicpc.net/problem/9613
GCD 합

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

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else
		return gcd(b, a % b);
}

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		long long sum = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				sum += gcd(a[i], a[j]);
			}
		}
		cout << sum << endl;
	}
	return 0;
}

---

소수

소수를 찾을 때, 예를 들어 n이 주어진 경우 2 ~ n-1을 브루트 포스로 모두 검사할 필요가 없다.
n이 소수가 되려면, 2보다 크거나 같고, 루트n 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
즉, 약수를 나열했을 때 절반까지만 검사해도 모두 검사하는 것과 같다.

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

위의 알고리즘, 어떤 수 n이 소수인지 아닌지 판별하는데 걸리는 시간 복잡도는 O(root_N)이다.
주의 할점은 i*i <= n, 부등호이다.

https://www.acmicpc.net/problem/1978
소수 찾기

#include <iostream>
using namespace std;

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

int main() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (prime(a))
			ans += 1;
	}
	cout << ans << '\n';
	return 0;
}

---

에라토스테네스의 체

어떤 수 n이 소수인지 판단하는 알고리즘의 시간 복잡도의 경우 루트N이었다.
그럼 1~n까지의 수가 주어졌을 때 소수를 구하는 알고리즘의 시간 복잡도는 얼마일까?
수가 총 n개이기 때문에 O(N_root_N)의 시간이 걸린다.

따라서 이런 경우 에라토스테네스의 체라는 알고리즘이 필요하다.

에라토스테네스의 체의 순서도는 다음과 같다.
1. 2부터 N까지 모든 수를 쓴다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 이제 그 수의 배수를 모두 지운다. -> 2번으로

배수를 지움으로써, 약수가 있는 수를 모두 제거한다.

int prime[100]; //소수 저장용
int pn=0; //소수 개수
bool check[101]; //지워진 경우 true
int n = 100; // 100까지 소수를 구하고 싶어
for(int i = 2; i<=n; i++){
	if(check[i] == false){
    	prime[pn++] = i;
        for(int j = i*i; j<=n; j+=i){
         check[j] = true;
        }
    }
}

nested for문에서 j = i2가 아니라 ii를 사용한 이유는 그 전까지의 i의 배수는 이전 단계에서 이미 지워져 있기 때문이다.

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

#include <cstdio>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1]; // true 지워짐
int main() {
	check[0], check[1] = true;
	for (int i = 2; i * i <= MAX; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}
	int m, n;
	scanf("%d %d", &m, &n);
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			printf("%d\n", i);
		}
	}
	return 0;
}

에라토스테네스의 체에서 가장 주의할 점은 반드시 2부터 시작해야 한다는 것이다.
다 구해놓고 걸러서 사용하면 된다.