[JAVA] 백준 1929 소수 구하기

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

 

풀이 과정 

 

-에라토스테네스의 체 이용 

 

에타토스테네스의 체 

 

[알고리즘] 에라토스테네스의 체 알고리즘(C언어) (tistory.com)

[알고리즘] 에라토스테네스의 체 알고리즘(C언어)

 

- 2부터 시작하는 양의 정수들 중에서 소수(prime number)인 것을 찾아내는 알고리즘 중 하나 

- 2부터 시작하여, 그 다음 소수의 배수를 모두 지워나가면서 소수를 찾아내는 방식으로 동작

 

- 먼저 2부터 n까지의 모든 정수를 배열에 저장 

- 배열에서 2를 제외한 2의 배수를 모두 지움 

- 다음으로, 배열에서 3을 제외한 3의 배수를 모두 지움

- 이렇게 배열에서 지워지지 않은 가장 작은 수를 다음 소수로 간주하고, 그 수를 제외한 그 수의 배수를 모두 지움 

- 이 과정을 반복하여, 배열에서 지워지지 않은 수가 소수가 됨 

 

정답 

 

import java.util.Scanner;

public class Main {
    
    public static void Eratosthenes(int arr[], int n)
    {
        //배열 초기화 
        //2부터 n까지의 정수를 배열에 저장 
        for(int i=2; i<=n; i++)
        {
            arr[i] = i;
        }
        
        //에라토스테네스의 채 알고리즘
        //2부터 시작하여 2의 배수를 모두 지움, 3부터 시작하여 3의 배수를 모두 지움
        //... 위 과정 반복
        for(int i=2; i*i<=n; i++)
        {
            //배열의 값이 0인 경우는 이미 지워진 수 -> 무시하고 다음 인덱스로 
            if(arr[i] ==0) continue;
            for(int j=i*2; j<=n; j+=i)
            {
                arr[j] = 0;
            }
        }
    }
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        if(m<2)
        {
        	m=2;
        }
        
        int arr[] = new int[n+1];
        Eratosthenes(arr,n);
        for(int i=m; i<=n; i++)
        {
            if(arr[i]!=0)
            {
                System.out.println(arr[i]);
            }
        }

    }
}