[정수론] 소인수분해

백준 11653 소인수분해

https://www.acmicpc.net/problem/11653

1은 소인수분해하면 아무것도 없어야 한다. 1로 출력하면 틀림.

for문에서 N이 계속해서 변하는 것이 특이함.

package com.company;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        if(N==1) return;
        

        for(int i=2; i<=N; i++){
            if(N%i==0){
                System.out.println(i);
                N=N/i;
                i--;
            }
        }
    }
}

처음풀이

에라토스테네스의 체로 소수를 전부 다 구한다음 그것들로만 나눈다.

근데 연산과정을 보면 체 하는것만 해도 그냥 소인수 바로 구하는 것 보다 많음.

이것도 맞긴 한데 1처리를 안해서 틀린거였다.

package com.company;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] num = new int[N+1]; //체크되면 1
        List<Integer> primeNums = new ArrayList<>();

        setPrime(num, primeNums, N);

//        System.out.println(primeNums);

        if(N==1) return;

        for(int i=0; i<primeNums.size(); i++) {

            if(N%primeNums.get(i)==0) {
                System.out.println(primeNums.get(i));
                N = N/primeNums.get(i);
                i--;
            }
        }

    }


    static void setPrime(int num[], List primeNums, int N) {

        for(int start=2; start<=N; start++) {

            if(num[start]==1) continue;
//       System.out.println("소수: "+start);
            primeNums.add(start);

            if(Math.sqrt(N) < start) continue; //루트 엔 뒤쪽은 삭제할 필요가 없음

            for(int i=start; start*i<=N; i++) {
//          System.out.println("-" + start*i);
                if(num[start*i]==0) {
                    num[start*i]=1;
                }
            }
        }
    }
}