Algorithm

[Programmers] 소수 찾기 - java

향찡 2022. 7. 23. 14:41

https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

소수 찾기 (완전 탐색)

배운 것

에라토스테네스의 체

소수 찾기

재귀를 통한 숫자 조합

에라토스테네스의 체 란?

수학에서 에라토스테네스의 체는 소수를 찾는 방법을 말한다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이  m=ab라면 a와b 중 적어도 하나는 Math.sqrt(n) 이하(루트 n)이다. 즉, n보다 작은 합성수 m은 Math.sqrt(n) 보다 작은 수의 배수만 체크해도 된다. 

풀이에 대한 설명은 아래 소스코드 주석을 확인하면 된다.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

// 소수 찾기
public class Problem8 {

    Set<Integer> numberSet = new HashSet<>();

    public static void main(String[] args) {
        Problem8 problem8 = new Problem8();
        problem8.solution("17");
    }

    public int solution(String numbers) {
        int count = 0;

        // 만들 수 있는 숫자 조합하기(재귀)
        recursive("", numbers);
        System.out.println(numberSet); // 출력해 보기

        // 만든 숫자가 소수인지판단한다 - 에라토스테네스의 체 (특정 숫자의 루트값까지만 확인해서 소수인지 판별)
        Iterator<Integer> it = numberSet.iterator();
        while (it.hasNext()) {
            int number = it.next();
            if (isPrime(number)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPrime(int number) {
        // 1. 0과 1은 소수가 아니다.
        if (number == 0 || number == 1) {
            return false;
        }

        // 2. 에라토스테네스의 체의 limit을 계산한다.
        int limit = (int) Math.sqrt(number); // root를 씌운값

        // 3. 에라토스테네스의 체에 따라 limit까지만 배수 여부를 확인한다.
        for (int i = 2; i <= limit; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    private void recursive(String comb, String others) {
        // 1. 현재 조합을 set에 추가한다.
        // set을 통한 만든 숫자 중복제거
        if (!comb.equals("")) {
            numberSet.add(Integer.valueOf(comb));
        }
        // 2. 남은 숫자 중 한개를 더 해 새로운 조합을 만든다.
        for (int i = 0; i < others.length(); i++) {
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));
        }
    }
}

Reference