[수학] 소수 판별하기, 모든 소수 구하기

1. 주어진 수가 소수인지 판별하기

- 약수 구할 때 제곱근을 이용하는 방식과 같음

- 2부터 n에 루트를 씌운 값까지만 반복하면서 나누어 떨어지는 값이 있으면 반복문 종료 

def is_prime_num(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

※ 여기서는 n이 1일 때를 고려하고 있지 않은데, 1은 소수가 아니므로 n이 1일 수도 있으면 if로 처리해줘야 함

 

2. 모든 소수 구하기

- 에라토스테네스의 체

1. 2부터 n까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

2-1. 1부터 주어진 수 사이의 모든 소수 (n이 소수일 경우 n을 포함하지 x)

def all_prime_num(n):
    a = [True] * n  # 전부 소수로 간주해서 초기화

    for i in range(2, int(n ** 0.5) + 1):
        if a[i]:    # i가 소수인 경우
            for j in range(i+i, n, i):  # i 제외 i의 배수들을 False 판정
                a[j] = False

    return [i for i in range(2, n) if a[i]]  # 1을 제외하기 위해 2부터

2-2. 1부터 주어진 수까지의 모든 소수 (n이 소수일 경우 n을 포함)

def all_prime_num(n):
    a = [True] * (n + 1)  # 전부 소수로 간주해서 초기화

    for i in range(2, int(n ** 0.5) + 1):
        if a[i]:    # i가 소수인 경우
            for j in range(i+i, n + 1, i):  # i 제외 i의 배수들을 False 판정
                a[j] = False

    return [i for i in range(2, n + 1) if a[i]]  # 1을 제외하기 위해 2부터