[이것이 코딩 테스트다 with Python]_37_기타 알고리즘_소수 판별 알고리즘

220213 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=CyINCmJPjfM&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=37 

 

 

 

 

1. 소수 (Prime Number)

: 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수

: 나누어떨어지지 않는 자연수

ex) 7은 1, 7 말고 나누어떨어지지 않아므로 소수!

 

 

• python

import math

# 소수 판별 함수 ( 2이상 자연수)
def is_prime_number(x):
    # 2부터 (x-1)까지의 모든 수 확인
    for i in range(2,x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

• c++

#include <bits/stdc++.h>

using namespace std;

// 소수 판별 함수(2이상의 자연수에 대하여)
bool isPrimeNumber(int x) {
    // 2부터 (x-1) 까지의 모든 수 확인하며
    for (int i = 2; i < x ; i++) {
        // x가 해당 수로 나누어떨어진다면
        if (x % i == 0) {
            return false; // 소수가 아님
        }
    }
    return true; // 소수임
}

int main() {
    cout << isPrimeNumber(4) << '\n';
    cout << isPrimeNumber(7) << '\n';

• java

import java.util.*;

class Main {
    // 소수 판별 함수(2이상의 자연수에 대하여)
    public static boolean isPrimeNumber(int x) {
        // 2부터 (X-1) 까지의 모든 수 확인하며
        for (int i = 2; i < x ; i++) {
            // x가 해당 수로 나누어떨어진다면
            if (x % i == 0) {
                return false; // 소수가 아님
            }
        }
        return true; // 소수임
    }

    public static void main(String[] args) {
        System.out.println(isPrimeNumber(4));
        System.out.println(isPrimeNumber(7));
    }
}

 

=> 2부터 x-1 까지의 모든 자연수에 대해 연산 수행

=> 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X)

 

 

 

 

 

 

 

2. 약수의 성질

: 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대칭에 이루는 것!

EX) 16의 약수는 1, 2, 4, 8, 16

=> 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면됨!

 

 

 

 

 

+) 소수의 판별  ( 개선된 알고리즘)

• python

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

• c++

#include <bits/stdc++.h>

using namespace std;

// 소수 판별 함수(2이상의 자연수에 대하여)
bool isPrimeNumber(int x) {
    // 2부터 x의 제곱근까지의 모든 수를 확인하며
    for (int i = 2; i <= (int) sqrt(x); i++) {
        // x가 해당 수로 나누어떨어진다면
        if (x % i == 0) {
            return false; // 소수가 아님
        }
    }
    return true; // 소수임
}

int main() {
    cout << isPrimeNumber(4) << '\n';
    cout << isPrimeNumber(7) << '\n';
}

• java

import java.util.*;

class Main {
    // 소수 판별 함수(2이상의 자연수에 대하여)
    public static boolean isPrimeNumber(int x) {
        // 2부터 x의 제곱근까지의 모든 수를 확인하며
        for (int i = 2; i <= Math.sqrt(x); i++) {
            // x가 해당 수로 나누어떨어진다면
            if (x % i == 0) {
                return false; // 소수가 아님
            }
        }
        return true; // 소수임
    }

    public static void main(String[] args) {
        System.out.println(isPrimeNumber(4));
        System.out.println(isPrimeNumber(7));
    }
}

 

=> 2부터 X의 제곱근 (소수점 이하 무시) 까지의 모든 자연수에 대해 연산 수행

=> 시간 복잡도는 O(N^1/2)