[코테]01-소수

Hyewon·2021년 3월 4일

codingtest

목록 보기

3/25

소수
- Prime Number
- 약수가 1과 자기 자신 밖에 없는 수.
- 소수가 N이라면, 약수로 1,N만 있어야함.
- 2-(N-1)로 나누어 떨어지지 않으면 N을 소수라고 함.

1. 어떤수 N이 소수인지 ?

소수의 정의
2-(N-1)까지 나누어 떨어지는지 확인 -> O(N)
2-루트N -> 검사 O(루트N)
어떤수(N)가 약수인지 아닌지 판별하려면 루트N까지만 판별하면 되기 때문.
근데 0~루트N까지 검사할 필요없음.
2-루트N까지만 검사하면 됨
i = 2 - 루트N
- i*i <= x <- 제곱보다 x보다 작거나 같을때까지

1) 소수찾기 (백준 1978번)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int count=0;
		
		for(int i=0;i<num;i++) {
			if(isPrime(sc.nextInt())){
				count++;
			}
		}
		System.out.println(count);
	}
	
	static boolean isPrime(int num) {
		if(num==1)
			return false;
		
		for(int i=2;i*i<=num;i++) {
			if(num%i==0)
				return false;
		}
		return true;
	}
}

=> 해결방법 : 위의 어떤 N이 소수인지 확인하는 것을 바탕으로 풀었다. 소수인지 확인할 수 있는 함수를 하나 만들어서 1이면 false, 2부터 시작해서 i*i<=num까지 for문을 돌려서 그 num값이 i로 나누어 떨어지면 소수가 아니기 때문에 false를 주고 조건에 하나도 걸리지 않으면 true를 주었다.

2) 소수 (백준 2581번)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int sum=0, min=Integer.MAX_VALUE;
		
		for(int i=a;i<=b;i++) {
			if(isPrime(i)){
				sum +=i;
				if(min==Integer.MAX_VALUE)
					min=i;
			}
		}
		if(sum==0) {
			System.out.println(-1);
		}else {
			System.out.println(sum);
			System.out.println(min);
		}
	}
	
	static boolean isPrime(int num) {
		if(num==1)
			return false;
		else if(num==2)
			return true;
		for(int i=2;i*i<=num;i++) {
			if(num%i==0)
				return false;
		}
		return true;
	}
}

=>해결방법 : 위 코드를 살짝만 응용해서 풀었다.
최소값은 어차피 맨 첫 소수이기 때문에 그냥 max값을 주고 그 값일때 i를 넣어주었다.

3) 소인수분해(백준 11653번)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int i=2;
		while(i<=a) {
			if(a%i==0) {
				System.out.println(i);
				a/=i;
			}else {
				i++;
			}
		}
	}
}

=>해결방법 : 간단한 문제였다. 2부터 시작해서 i로 나누어떨어지면 a/=i를 해주고 나누어떨어지지않으면 ++해주면 된다.

2. N이하의 모든 소수를 구하는 방법

에라토스테네스의 체

2부터 N까지 모든 수를 쓴다.
아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
그 수는 소수이다.
이제 그 수의 배수를 모두 지운다.
1배열) 수를 지웠는지 아닌지 -> 지움 : true 지우지 않음:flase
2배열) 소수의 목록을 유지할 배열 필요.
check[i]=true인 경우에 i가 지워짐.

1) 에라토스테네스의 채 (백준 1929번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static boolean[] num;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        num = new boolean[N+1];
        getPrimeNum(); 
        
        for(int i = M; i <= N; i++) {
            if(!num[i]) {
            	System.out.println(i);
            }
        }
        br.close();
    }
    
    public static void getPrimeNum() {
    	num[1] = true;
        
        for(int i= 2; i < num.length; i++) {
            for(int j = 2; i*j < num.length; j++) {
            	num[i*j] = true;
            }
        }
    }
}

=>배열을 2개 만들어서 하라고 했는데 굳이 나누지 않아도 될 것 같아서 이렇게 작성했다.