정리

약수

개념

어떤 수를 나누어 나머지가 없이 떨어지게 하는 수

약수의 개수 구하기

int divisorCount = 0;

반복문1

for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        divisorCount++;
    }
}

반복문2

for (int i = 1; i <= Math.sqrt(n); i++) {
    if (i == Math.sqrt(n)) divisorCount++;
    else if (n% i == 0) divisorCount += 2;
}

약수 모두 구하기

List<Integer> divisors = new ArrayList<>();

반복문1

for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        divisors.add(i);
    }
}

반복문2

for (int i = 1; i <= Math.sqrt(n); i++) {
    if (i == Math.sqrt(n)) {
        divisors.add(i);
    } else if (n % i == 0) {
        divisors.add(i);
        divisors.add(n / i);
    }
}

Collections.sort(divisors);

최대 공약수

개념

정수 a, b가 주어지고 r은 a % b 일 때, GCD(a, b) = GCD(b, r)

구현

재귀

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

반복문

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

최소 공배수

개념

A = ad, B = bd에서 a, b는 서로소이고, d는 최대공약수이다
따라서 a * b * d 이고, 이는 (A * B / d) 이므로 최대공약수를 구함

구현

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

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

소수

개념

소수는 1 이상의 자연수에서 1과 자기 자신만을 약수로 갖는 자연수

소수 판독

Set<Integer> primeNumbers = new LinkedHashSet<>();

반복문1

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

반복문2

for (int i = 2; i <= Math.sqrt(number); i++) {
    if (number % i == 0) {
        return false;
    }
}

N 이하의 모든 소수 구하기

반복문1

for (int i = 2; i <= N; i++) {
    boolean flag = true;
    for (int j = 2; j < i; j++) {
        if (i % j == 0) {
            flag = false;
            break;
        }
    }
    if (flag) primeNumbers.add(i);
}

반복문2

for (int i = 2; i <= N; i++) {
    boolean flag = true;
    for (int j = 2; j <= Math.sqrt(i); j++) {
        if (i % j == 0) {
            flag = false;
            break;
        }
    }
    if (flag) primeNumbers.add(i);
}

에라토스테네스의 체

boolean[] primes = new boolean[N + 1];  
for (int i = 2; i <= N; i++) {  
    primes[i] = true;  
}  

for (int i = 2; i <= Math.sqrt(N); i++) {  
    if (!primes[i]) continue;  
    for (int j = i * i; j <= N; j+=i) {  
        primes[j] = false;  
    }  
}  

for (int i = 0; i <= N; i++) {  
    if (primes[i]) {  
        primeNumbers.add(i);  
    }  
}

소인수분해

개념

어떤 수를 소수(Prime)인 인수로 분해하는 것

구현

List<Integer> factors = new ArrayList<>();
for (int i = 2; i < Math.sqrt(n); i++) {
    while(n % i == 0) {
        factors.add(i);
        n /= i;
    }
}

if (n > 1) {
    factors.add(n);
}

각 소수가 몇번씩 들어있나 구현

Map<Integer, Integer> factors = new HashMap<>();
for (int i = 2; i < Math.sqrt(n); i++) {
    while(n % i == 0) {
        factors.put(i, factors.getOrDefault(i, 0) + 1);
    }
}

if (n > 1) {  
    factors.put(n, factors.getOrDefault(n, 0) + 1);  
}