[Algorithm] 소수 구하기(에라토스테네스의 체) - JAVA

소수를 구해야하는 알고리즘을 구현해야 할때마다 헷갈려서 정리를 해두려고 한다. 까먹지말자!

에라토스테네스의 체를 사용하여 구하자

import java.util.*;

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

            for(int i=0; i< prime.length; i++){

                if(prime[i] == false) System.out.println(i); // 소수일 경우 출력

            }
    
    }
    
    public static void isPrime(int N){
    	
        prime = new boolean[N+1]; // 0부터 N까지
        
        // 소수라면 false, 소수가 아니면 true
        if(N<2) return;
        
        prime[0] = prime[1] = true;
        
        // 제곱근 함수 : Math.sqrt()
        
        for(int i=2; i<=Math.sqrt(N); i++){
        	if(prime[i] == true) continue;
            
            // i의 배수들을 제외시키기
            for(int j=i; j<prime.lenth; j=j+i){
            	prime[j] = true;
            }
        
        }
    
    }
}

 

위의 예는 n까지의 숫자 중에서 소수가 몇 개인지를 체크하는 문제였고, 소수여부를 판단하기 위한 코드를 작성하기 위해서는 아래와 같이 작성하여 체크하면 된다.

public static boolean isPrime(int n){
	if(n<2) return false; // 소수 아님
    
    for(int i=2; i<Math.sqrt(n); i++){
    	if(n % i == 0) return false; // 소수 아님
    }
    
    return true;
}

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

프로그래머스