소수

소수를 구하는 방법에는 세 가지가 있다.

 

 

 

① (2부터 자기자신-1) 까지의 모든 수로 나누어보기

 

소수의 정의 = 1과 자기자신으로 나누어떨어지는 수 를 이용하는 방법!

모든 수로 나누어 보는 과정을 거쳐야하기 때문에, 시간초과 위험 + 비효율적이다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		
        //2부터 num-1 까지의 모든 수를 체크
        for(int i=2; i<=num; i++){
        	if(check(i))
            	System.out.println(i);
        }
	}
    
	public static boolean check(int num){
		boolean ans = false;
        int i=2;
		
        //나머지=0이면 소수X
		while(i<num){ 
			if(num%i == 0) 
				break;
			else i++;
		}

		if(i == num) //소수O
			ans = true;
        
        return ans;
	}

 

 

② 제곱근 이용하기 - (2부터 제곱근)까지의 수로 나누어보기

 

①처럼 모든 수로 나누어보지 않고, 제곱근까지의 수까지만 체크하면 된다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		//2부터 루트num까지의 수만 체크
        //Math.sqrt() 리턴값은 double형이다. int형으로 바꾸어주기
		
        for(int i=2; i<=(int)Math.sqrt(num); i++){
        	if(check(i))
            	System.out.println(i);
        }
	}

	public static boolean check(int num){
		boolean ans = false;
		int i=2;
        
		while(i<num){
			if(num%i == 0)
				break;
			else i++;
		}

		if(i == num)
			ans = true;

		return ans;
	}

 

 

③ 에라토스테네스의 체

 

①방법 : num까지의 모든 수를 돌며 소수인지 확인한다. ( 2~num-1까지의 수로 나누어보는 과정 ) - 비효율적

②방법 : Math.sqrt(num)까지의 수를 이용해 소수인지 확인한다. - 효율적

 

에라토스테네스의 체는 2의배수, 3의배수, ... , x의 배수인 수들을 제외하고 나머지 수를 소수로 판단한다.

조금더 풀어서 설명하면

2를 제외한 모든 2의 배수를 체크한다. -> 3을 제외한 모든 3의 배수를 체크한다. -> ... 와같은 과정을 통해 소수가 아닌 수를 걸러낸다. 

나머지 체크가 안된 수 = 소수 로 판단한다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		//2~num까지의 수가 들어있는 배열 만들기
		//check[i]=false 이면 소수인거
		
        boolean[] check = new boolean[num+1];
		for(int i=2; i<=num; i++){
			check[i] = false;
		}

		for(int i=2; i<=(int)Math.sqrt(num); i++){
			if(check[i]) //이미 체크한거는 다시 체크X
				continue;
			for(int j=i+i; j<=num; j+=i){
            	if(!check[j])
                	check[j] = true; //j를 제외한 j의 배수 체크하기
			}
		}

		for(int i=2; i<=num; i++){
			if(!check[i])
				System.out.println(i);
		}
	}

 

 

 

소수 관련 문제 (백준)

1929번: 소수 구하기

1978번: 소수 찾기

2581번: 소수

1747번: 소수&팰린드롬

1990번: 소수인팰린드롬

4948번: 베르트랑 공준