JAVA 코딩테스트 :: 소수 구하기

📝 소수 구하기

• 소수 : 1과 자기 자신으로만 나누어지는 수
  * 1은 소수에서 제외
• 직접 구현
• Math.sqrt() 메소드 사용
• 에라토스테네스의 체
  
  

💡 직접 구현

• N 보다 작은 자연수들로 나누는 방식
• 시간복잡도: O(N²)
  
  

▶ 예시

• N 이하의 모든 소수 출력

public static void Prime(int num) {
    if(num < 2) // 0과 1은 소수가 아님
        return;
    else if (num == 2) { // 2는 소수 
        System.out.println(num);
        return;
    }

    for(int i = 2; i < num; i++) {
        if(num % i == 0) // 소수가 아닐 경우
            return;
    }

    // 위 반복문에서 약수를 갖고 있지 않는 경우 소수
    System.out.println(num);
    return;
}

💡 Math.sqrt()

• √N 이하의 자연수들로 나누는 방식
• sqrt() : 제곱근
• 제곱근 이하로 범위가 줄어들게 되는 이유: 소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문
• 시간복잡도: O(N√N)
  
  

▶ 예시

• N 이하의 모든 소수 출력

public static void Prime(int num) {
	if(num < 2) // 0과 1은 소수가 아님
    	return;
	else if(num == 2) {  // 2는 소수
    	System.out.print(num);
    	return;
	}

	for(int i = 2; i <= Math.sqrt(num); i++) {
   		if(num % i == 0) // 소수가 아닐 경우
        	return;
	}

	// 위 반복문에서 약수를 갖고 있지 않는 경우 소수
	System.out.print(num);
	return;
}

💡 에라토스테네스의 체

• i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식
• 시간복잡도: O(Nlog(log N))
  
  

▶ 예시

• N 이하의 모든 소수를 구하라

public class sifter {
    public static boolean[] prime;	// 소수를 체크할 배열
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        Prime(N);

        for(int i = 0; i < prime.length; i++) {
            if(prime[i] == false) {	// 소수(false)일 경우 출력
                System.out.println(i);
            }
        }
    }

    // N 이하 소수 생성 메소드 
    // 소수면 false, 소수가 아니면 true
    public static void Prime(int N) {
        prime = new boolean[N+1];	 // 0 ~ N
        prime[0] = prime[1] = true;  // 숫자 0과 1은 소수가 아님
        
        if(N < 2)  // N이 1 이하일 경우
            return;

        // √N(제곱근) 이하까지 반복 
        for(int i = 2; i <= Math.sqrt(N); i++) {
            if(prime[i] == true)  // 이미 한번 체크된 배열이면 continue
                continue;

            // i의 배수라면 소수가 아니므로 true
            for(int j = i * i; j < prime.length; j = j+i) {
                prime[j] = true;
            }
        }
    }
}