[Algorithm] 소인수분해 / 소수 (에라토스테네스의체)

소인수분해

• 소수인 인수들만의 곱으로 분해하는 것
  
  

for(int i=2; i<=n; i++){...}

위처럼 n까지 사용하여 전체를 반복문을 돌리는 것보다

for(int i=2; i<=Math.sqrt(n); i++){...}

인수는 $\sqrt{n}$ 보다 작거나 같기 때문에 n까지 굳이 계산할 필요가 없다

범위를 제곱근까지로 제한하여 계산하는 것이 더 좋은 효율성

백준 11653 소인수분해

• 문제풀이

import java.util.Scanner;
import java.lang.Math;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
       
        for(int i=2; i<=Math.sqrt(n); i++){
            while(n%i == 0){
                System.out.println(i);
                n/=i;
            }
        }
        if (n!=1) { //나뉜 값이 1이 아니라면 소인수로 출력
			System.out.println(n);
		}
        sc.close();
    }
}

소수구하기

• 에라토스테네스의 체

: 정수 n에 대하여 n의 제곱근까지의 배수들을 전부 제외시키고 나면 소수만 남는다는 알고리즘

반복문을 사용하여 소수를 구하는 것보다 훨씬 좋은 효율성

백준 1929 소수구하기

• 문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class primeNumber {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int m = Integer.parseInt(str[0]);
        int n = Integer.parseInt(str[1]);

        StringBuilder sb= new StringBuilder();
        //에라토스테네스의 체
        boolean[] prime = new boolean[n+1]; // 0~n까지 bool배열 선언
        Arrays.fill(prime,true); //일단 전부 소수로 초기화

        prime[0] = false;
        prime[1] = false;
        for(int i =2; i*i<=n;i++){ // 
            if(!prime[i]) continue; //이미 지정된 원소이면 skip
            for(int j= i*i; j<=n; j+=i){
                prime[j] = false; //배수는 소수에서 제외
            }
        }
        for(int i=m; i<=n; i++){
            if(prime[i]){ //소수만 추가
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}