구현/Degree

소수관련 문제 1 - 소수 판별법

#include <cmath>
int x = 10;
sqrt(x); //x의 제곱근
pow(x, 2); // x의 n제곱 

for(int i=2; i<sqrt(x); i++) {
	if(x % i == 0) {
		sosu = false;
	}
}

어떤 수가 소수인지 확인 하는 알고리즘
어떤 x가 소수인지 확인할 때는 2부터 x의 제곱근 까지만 나누어 보는 것으로 확인할 수 있다.

백준 1929 - 소수 구하기

소수관련 문제2 - 에라토스테네스의 체

int check[1000000] = { 1, 1, 0 };
for(int i=2; i<= sqrt(n); i++) {
    if(check[i] == 0) {
        for(int j= i + i; j <= n; j += i) {
            check[j] = 1;
        }
    }
}

n이 주어졌을 때, 1 부터 n 까지의 모든 소수를 구하는 방법
2 부터 n의 제곱근까지 검사하여 소수들의 배수를 지워 나간다.

백준 1644 - 소수의 연속합

소수관련 문제 3 - 소수 판별법+에라토스테네스의 체로 소수 판별하기

int check[1000000000] = { 1, 1, 0 };
for(int i=2; i<= sqrt(n); i++) {
    if(check[i] == 0) {
        for(int j= i + i; j <= n; j += i) {
            check[j] = 1;
        }
    }
}

for(int i=2; i<1000000000; i++) {
	if(!check[i]) v.push_back(i);
}

for(int i = 0; i < v.size(); i++) {
	if(target % v[i] == 0) break;
}

이 방법은 배열의 최대 크기보다 훨씬 큰 수를 소수 판별할때 사용한다.
먼저 에라토스테네스의 체를 이용하여 check배열을 초기화한다. 최대한 소수를 벡터에 담고, 구하려는 수를 소수들로 나누어주며 나누어진다면 소수가 아니다. 소수가 아닌 수들은 소수를 약수로 갖기 때문이다.

백준 15711 - 환상의 짝꿍

유클리드 호제법

int get_gcd(int a, int b){
    if(a<b){
        int temp = a;
        a = b;
        b = temp;
    }
    
    while(b!=0){
        int n = a%b;
        a = b;
        b = n;
    }
    return a;
}

두 수의 최대공약수와 최소공배수를 구하는 알고리즘

백준 2609 - 최대공약수와 최소공배수

백준 2485 - 가로수