🎈소수 구하는 알고리즘

✏️ ✓N 이하의 자연수들로 모두 나누는 방법

• p x q = N 을 만족할 때

  1 x 16
  2 x 8
  3 x 6
  4 x 4
  8 x 2
  16 x 1

• p가 증가한다면 q가 감소
• 반대로 p가 감소한다면 q가 증가
• 즉, ✓N이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1과 N을 제외한 다른 자연수가 N의 약수이므로 소수가 아니게 됨
• 이를 알고리즘으로 구현한다면

  // 소수만 출력 
  import java.util.Scanner;
  
  public class Prime_2 {
  	public static void main(String[] args) {
  
  		Scanner in = new Scanner(System.in);
  
  		int N = in.nextInt();
         
  		// 0 ~ N 까지 수 중 소수를 구하는 반복문        
  		for(int i = 0; i <= N; i++) {
  			make_prime(i);
  		}
     
  	}
  
  	// 소수 생성 메소드 
  	public static void make_prime(int number) {
  
  		// 0 과 1 은 소수가 아니므로 종료
  		if(number < 2) {
  			return;
  		}
  		
  		// 2 는 소수다
  		if(number == 2) {
  			System.out.println(number);
  			return;
  		}
  		
         
  		// 제곱근 함수 : Math.sqrt()
  		for(int i = 2; i <= Math.sqrt(number); i++) {
         
  			// 소수가 아닐경우 종료
  			if(number % i == 0) {
  				return;
  			}
  		}
  		// 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
  		System.out.println(number);
  		return;
  	}
  }

✏️ 에라토스테네스의 체

• 소수를 구하는 대표적인 방법 중 하나
• K=2부터 ✓N 이하까지 반복하여 자연수들 중 K를 제외한 K의 배수들을 제외시킴

  1. k = 2일 때, 2를 제외한 2의 배수를 모두 지운다
  2. K = 3일 때, 3을 제외한 3의 배수를 모두 지운다
  3. K = 4일 때 4는 이미 K = 2에서 제외되어 스킵
  4. 이와 같은 방식으로 k = ✓N까지 반복

import java.util.Scanner;
 
public class Prime_3 {
 
    public static boolean[] prime;	// 소수를 체크할 배열
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		
		make_prime(N);
 
		for(int i = 0; i < prime.length; i++) {
			if(prime[i] == false) {	// 소수(false)일 경우 출력
				System.out.println(i);
			}
		}
	}
 
	// N 이하 소수 생성 메소드 
	public static void make_prime(int N) {
		
		prime = new boolean[N + 1];	// 0 ~ N
 
		/*
		소수가 아닌 index = true
		소수인 index = false
		*/
		
		// 2 미만의 N 을 입력받으면 소수는 판별할 필요 없으므로 바로 return
		if(N < 2) {
			return;
		}
        
		prime[0] = prime[1] = true;
		
        
		// 제곱근 함수 : Math.sqrt()
		for(int i = 2; i <= Math.sqrt(N); i++) {
        
			// 이미 체크된 배열이면 다음 반복문으로 skip
			if(prime[i] == true) {
				continue;
			}
        
			// i 의 배수들을 걸러주기 위한 반복문
			for(int j = i * i; j < prime.length; j = j+i) {
				prime[j] = true;
			}
		}
 
	}
 
}