에라토스테네스의 체, 소인수 분해

이 글은 공부한 내용을 기반으로 적는 글이오니, 건전한 비판은 언제든 환영합니다.

 

에르토스테네스의 체

에르토스테네스의 체는 언제 알고리즘을 사용하게 될까?

 

예를 들면 1~100 까지의 리스트에 담겨있는 정수가 있다.

여기서 문제가 소수는 몇 개인가 확인해야 하는 문제가 주어진다면

 

단순히 생각하기로는 이중 for문으로 찾을 수 있지만 그러면 너무 시간이 거대하게 걸린다.

하나하나 비교를 하다보면은 불필요한 계산이 행하여 진다.

 

그래서 어떻게 작성을 할꺼면 먼저 2부터 시작하여서 2의 배수이면 계산이 안들어가고 그 다음에 3의 배수 5의 배수 방식으로 들어간다.

 

import java.util.ArrayList;

public class Eratosthenes {
    public static ArrayList<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        for (int p = 2; p * p <= n; p++) {
            System.out.println("Checking for prime: " + p);
            if (isPrime[p]) {
                System.out.println(p + " is prime. Removing its multiples.");
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.println("Found prime: " + i);
                primes.add(i);
            }
        }

        return primes;
    }

    public static void main(String[] args) {
        int n = 10;
        ArrayList<Integer> primes = sieve(n);
        System.out.println("Primes up to " + n + ": " + primes);
    }
}

코드와 같이 먼저 n만큼의 boolean list를 만들어서 false값을 준다 그리고 나서, 루트 i까지 계산을 한 다음에

2부터 3,5,7 ......... 방식으로 들어가고 중간에 배수가 있다고 한다면 그 다음으로 넘어간다.

 

이런 방식으로 n에서 소수를 구하라고 한다면 에르토스테네스의 체를 사용하면 된다

 

소인수 분해

 

소인수 분해는 주어진 자연수 n보다 작은 소수들의 곱으로 나눠지는 것이다.

예를 들면 n이 30이라고 주어졌을 때, 손으로 풀게 된다면 n이 30이 주어졌을 때, 

2/30 = 15

3/15 = 5

라고 계산 하면서 결과적으로 2*3*5로 나타날 수 있다

하지만 컴퓨터는 계산을 직관적으로 풀어내지 못 하기 때문에 일일히 대조를 해줘야 한다.

 

int n = 30;

for(int i = 2;n>1;){

if(n%i == 0)
	{ n = n/i;}
else{
	i++
}

방식으로 나눌 수 있을 것 이다.