에라토스테네스의 체 (소수를 찾는 방법)

 

에라토스테네스의 체란?

- 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.

- 어떤수( 소수를 구하고자 하는 값 )의 제곱근보다 작은 소수의 배수를 없애면 남은 수가 어떤수의 소수가 된다.

 

한마디로 어떤수가 100이라고 가정할때

100의 소수를 구하려면 매우 어렵지만 100의 제곱근인 10의 소수의 배수를 배제하고 나면

100의 소수만 남게된다는 방법이다.

 

 

 

 

 

 

에라토스테네스의 체 알고리즘 처리구조 

1. 요소의 소수의 배수를 제거하는 구조

2. 소수에 다음 소수를 대입하는 구조

3. 소수가 입력값 제곱근 이하일 때 반복하는 구조 

4. 소수인 첨자를 출력 

 

 

 

 

 

코드구현

// input
        Scanner sc = new Scanner(System.in);
        System.out.print("소수를 구할 값을 입력하세요 : ");
        int user = sc.nextInt();
        
       int[] arr = new int[user+1]; // 배열의 첨자를 소수로 나타내기 위해 + 1을 해줌 
        Arrays.fill(arr,1); // 배열의 모든값 1로 초기화      
        
        int k = 2; // 소수확인용 초기값 
        
        while( k * k <= user ) { // 초기값을 제곱한 값이 user값과 같거나 클때까지  
            
            int i = k; // 배수제거를 위한 변수 
            
            if(arr[k] == 1 ){ // 소수일때만 배수를 제거한다, 아닐경우 k++
                
                while( i <= user/k ) { //  k * i가 user값 이하 소수의 배수만 제거해야되기에, i를 user(입력값)/k(소수) 만큼 반복한다.
                 arr[k*i] = 0; // 소수값의 배수는 0으로 선언
                 i++;
                 }    
            }    
        k++; 
        }
        
        // 0과 1 제외 
        arr[0] = 0;
        arr[1] = 0;
        
 // output
         System.out.print(user+"값의 소수는 : ");
        for(int a=0; a < arr.length; a++){ 
            if(arr[a] == 1 ){
               System.out.print(a+",");     
            }
        }