[algorithm] 소수(prime number)에 대한 정의와 표현

728x90

소수 (Prime Number)의 정의

소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수

소수인지를 판별하는 알고리즘

기본적인 소수 판별 알고리즘(시간복잡도 O(n)

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

개선된 소수 판별 알고리즘(시간복잡도 O(n의 2분의1제곱))

import math

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

특정 숫자 x에 대하여 2~x-1까지 나누어떨어지는지 확인 해볼 필요없이

약수의 성질을 이용하여 x의 제곱근 까지만 나누어떨어지는지 확인해보면 그 뒤의 숫자는 확인해볼 필요가 없다.

*약수의 성질

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

ex)

16의 약수는 1,2,4,8,16 인데 1x16 2x8 4x4처럼 약수는 대칭을 이루어 곱셈연산을 하면 해당 수가 나온다.

관련 백준 알고리즘 문제

https://www.acmicpc.net/problem/1978

import math
#소수의 기본개념 1과 자기 자신만을 약수로 갖는 수
def is_prime_number():
    N = int(input())# 입력할 갯수를 받음
    numbers = map(int, input().split())# 입력할 갯수 만큼 정수를 받음
    prime_cnt = 0#받은 정수중에 소수의 갯수를 카운트 할 변수
    for num in numbers:
        div_cnt = 0#약수가 존재 할시 카운트 증가
        if num > 1:#입력 받은 정수가 1이면 소수 카운트를 증가시키지않고 pass, 2이상인 경우에 반복문과 조건문 적용
            for i in range(2, int(math.sqrt(num))+1):# 2부터 입력받은 정수의 제곱근 까지
                if num % i == 0:#입력받은 정수를 2부터 정수-1까지 나누어 나머지가 0인경우
                    div_cnt += 1#약수 카운트 증가
            if div_cnt == 0:#약수 카운트가 1개도 없을 시
                prime_cnt += 1#소수이므로 소수 카운트 증가
        else:
            pass
    return prime_cnt#소수 카운트 반환

print(is_prime_number())

1978번: 소수 찾기

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

www.acmicpc.net

https://www.acmicpc.net/problem/2581

def prime_sum_min(start = int(input()), end = int(input())):#함수의 매개변수(인자)에 대하여 인수를 직접 입력을 한다.
    prime_num_list = []
    for i in range(start, end+1):
        div_cnt = 0
        if i > 1:#범위 내의 숫자가 1인이상인 경우에만 반복문, 조건문 시행 1인경우 소수가아니므로 아무것도 하지 않는다.
            for j in range(2, i):
                if i % j == 0:
                    div_cnt += 1
                    break#약수 1개만 있어도 소수가 아님이 판별되므로 반복문 종료
            if div_cnt == 0:#약수가 1개도 없는 경우에 소수
                prime_num_list.append(i)#소수인 숫자 리스트에 저장

    if len(prime_num_list) > 0:#소수가 저장된 리스트가 0개 초과인 경우
        return sum(prime_num_list), min(prime_num_list)#리스트의 소수들의 합, 리스트중에서 가장 작은 소수를 튜플로써 반환
    else:
        return -1#소수가 저장된 리스트가 0개인 경우 -1을 반환

if type(prime_sum_min()) == tuple:#반환된 리스트가 0개 초과여서 반환을 2개이상하여 튜플이 반환된경우에
    for i in prime_sum_min():
        print(i)#튜플의 값을 줄바꿈하여 출력
else:
    print(prime_sum_min())#반환된 리스트가 0개인경우 있는 그대로 출력