쉽게 쉽게

[Java] 소수 구하기 본문

개발공부/Java

[Java] 소수 구하기

곱마2 2024. 9. 26. 09:45
반응형

▤ 목차

    1. 소수 구하기

    1. 방법1 (N까지 나누기)

    N 보다 작은 자연수들로 나눈 후 소수인지 아닌지 판별하는 알고리즘이다. 

    시간복잡도: O(N²)

    public boolean isPrime(int n) {
        if (n <= 1) return false;			// 1보다 작으면 false 반환
        for (int i = 2; i < n; i++) {		// 2보다 크고 n보다 작은 수로 나눈다.
            if (n % i == 0) return false;		// 만약 나누어 떨어지는 것이 있다면 false 반환
        }
        return true;				// 모두 나누고도 떨어지는 수가 없다면 true 반환
    }

    2. 방법2 (N의 제곱근보다 작은 수까지 나누기)

    첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 N의 제곱근(√) 까지만 나눈다.

    소수인지 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문에 제곱근까지만 판별하면 된다.

    일 때

    • 2×18=36
    • 3×12=36
    • 4×9=36
    • 6×6=36 (제곱근에서 대칭의 끝)

    즉, 약수는 작은 수와 큰 수로 짝을 이루고 있으며, 그 짝 중 하나는 항상 √보다 작거나 같고, 다른 하나는 √보다 크거나 같다.

    어떤 수 n이 소수가 아니라면, 최소 하나의 약수는 √ 이하의 범위에 존재해야 한다.

    36이 소수인지 확인하려고 한다면, 1부터 √ 36=6 까지만 나누어 보면 된다.

    2, 3, 4, 6 중 하나라도 나누어 떨어지면 36은 소수가 아니라고 결론 내릴 수 있다.

    왜냐하면, 그 이후에 나오는 약수들은 6보다 큰 값으로, 이미 6 이하에서 발견된 약수와 대칭적으로 대응되기 때문이다.

    예를 들어 12는 3에 대응하고, 18은 2에 대응한다.

    만약 이하의 값으로 나누어지지 않는다면, 그 이후의 값들로도 나누어지지 않는다.

    정리하자면

    1. 약수는 대칭적으로 존재한다. 예: a×b=n이면, a와 b 중 하나는 반드시 √ 이하다.
    2. 소수를 확인할 때는 까지의 수만 나눠보면 충분하다. 이후의 수로 나누어 떨어질 수 없다면, 그 이전에도 나누어 떨어지지 않았을 것이기 때문이다.

    따라서, 소수를 판별할 때는 굳이 그 수 자체까지 나눌 필요 없이 √ 까지만 나누어도 소수인지 아닌지를 알 수 있다.

    시간복잡도: O(N√N)

    public boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {			// n의 제곱근까지 나누기
            if (n % i == 0) return false;
        }
        return true;
    }

    3. 방법3 (에라토스테네스의 체)

    i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식

    먼저 가장 작은 수인 2를 소수로 등록한 후, 2의 배수를 지운다. -> 지우지 않은 수 중 가장 작은 수인 3을 소수로 등록한 후, 3의 배수를 지운다. -> 이를 계속 반복하여 남은 수가 소수이다.

    시간복잡도: O(Nlog(log N))

    public boolean[] sieveOfEratosthenes(int n) {
    
        //0부터 n까지의 수이기 때문에 n+1을 할당한다.
        boolean[] prime = new boolean[n+1];
        
        // 0과 1은 소수가 아니기 때문에 false를 저장한다.
        prime[0] = false;				
        prime[1] = false;
        
        // n의 제곱근까지 나눈다.
        for(int i = 2; i <= Math.sqrt(n); i++) {
            
            	// 소수라면 뒤에 오는 코드를 스킵한다.
    		if(prime[i] == true) {
    			continue;
    		}
            
    		// 2부터 배수에 해당하는 수를 true로 변환한다.
    		for(int j = i * i; j < prime.length; j = j+i) {
    			prime[j] = true;
            	}
    	}
        return prime;
    }

    https://sfida.tistory.com/28

     

    [Algorithm] JAVA 소수판별 - 에라토스테네스의 체

    ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로

    sfida.tistory.com

    잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.

     

    반응형

    '개발공부 > Java' 카테고리의 다른 글

    [Java] 최대공약수, 최소공배수 구하기  (0) 2024.09.20
    [Java] 약수의 개수 구하기  (0) 2024.09.15
    [Java] FILE 업로드(다중)  (0) 2024.04.28
    Map에 있는 값 형변환하기  (1) 2023.11.19
    입출력I/O  (0) 2023.03.31