소수 찾기 (for JAVA)

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        combination("", numbers, set);
        while(set.iterator().hasNext()) {
            int num = set.iterator().next();
            set.remove(num);
            if (num==2) answer++;
            if (num%2!=0 && isPrime(num)) {
                answer++;
            }            
        }
        return answer;
    }
    
    public void combination(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        if (!prefix.equals("")) {
            set.add(Integer.parseInt(prefix));
        }
        for (int i = 0;i< n;i++) {
            combination(prefix + str.charAt(i)
                       , str.substring(0,i) + str.substring(i+1,n)
                       , set);
        }
    }
    
    public boolean isPrime(int num) {
        if (num==0 || num==1 ) return false;
        for (int i=3;i<=(int) Math.sqrt(num); i+= 2) {
            if (num%i==0) return false;
        }
        return true;
    }
}

일단 적용해야 하는 알고리즘은 큰 수에서 소수찾기를 사용할때 가장 좋은 알고리즘은 에라토스테네스의 체 라는 알고리즘을 이용해야 한다

import java.util.*;

public class Programmers_even {
    public static int answer = 0;
    static ArrayList<Integer> arr = new ArrayList<>();
    static boolean[] check = new boolean[7];
    public static void main(String[] args) {
        int result = solution("17");
        System.out.println("result :" + result);
    }

    public static int solution(String numbers) {
        String temp = "";
        for (int i = 1;i <=numbers.length();i++) {
            combination(numbers, temp, i);
        }
        for (int n:arr) valid(n);
        return answer;
    }
    
    public static void valid(int num) {
        if (num == 0 || num == 1) return;

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

    public static void combination(String numbers,String str, int len) {
        if (str.length() == len) {
            if (!arr.contains(Integer.parseInt(str))) {
                arr.add(Integer.parseInt(str));
            }
        }
        for (int i = 0; i <numbers.length();i++) {
            if (check[i]) continue;
            str += numbers.charAt(i);
            check[i] = true;
            combination(numbers,str,len);
            check[i] = false;
            str = str.substring(0, str.length()-1);
        }
    }
}