파이썬 소수 판별 재귀함수 - paisseon sosu panbyeol jaegwihamsu

Question

목차 Show

통계, IT, AI
어떤 수가 소수인지 판별하기 본문
어떤 수가 소수인지 판별하기
[파이썬] 재귀함수를 통한 피보나치 수의 구현
피보나치 수
[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬

통계, IT, AI

어떤 수가 소수인지 판별하기 본문

IT/알고리즘

어떤 수가 소수인지 판별하기

Harold_Finch 2015. 12. 30. 10:31

오일러 프로젝트의 문제들 가운데에는 소수와 관련된 것들이 많다.

그래서 문제를 계속 풀기 전에 어떤 수가 소수인지 판별하는 코드를 작성하고 넘어가고자 한다.

소수는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 1보다 큰 자연수로 정의된다.

이 정의를 이용하여 어떠한 수가 소수인지 판별하기 위한 룰을 몇가지 생각해 볼 수 있다.

1. 2보다 작은 정수와 2를 제외한 짝수는 소수가 아니다.

ex) 16: 2로 나누어 떨어지므로 소수가 아니다.

2. 그 수의 제곱근보다 작거나 같은 소수로 나누어 떨어지면 소수가 아니다.

ex) 26: 2, 3, 5로만 나누어 떨어지는지 확인하면 된다.. 만약 4로 나누어 떨어진다면 2로도 나누어 떨어질 것이기 때문이다.

문제는 2번 룰에서, 소수를 찾기 위해서 소수를 찾아야 한다는 점이다.

이를 위하여 소수를 찾는 함수와 소수인지 판별하는 함수가 서로 재귀적으로 물리도록 하였다.

# -*- coding: utf-8 -*-

import numpy as np

class Prime:

	def __init__( self ):
	
		self.prime = [2,3]
		
	def is_prime( self, n ):
		
		if n < 2 : return False 
		
		# 기존의 소수 리스트에서 먼저 찾아본다.
		if n <= self.prime[-1] and n in self.prime: return True 
		
		# 그 수의 제곱근보다 작거나 같은 소수로 나누어 떨어지면 소수가 아니다.
		lim = np.floor( np.sqrt( n ) )
		
		if self.prime[-1] < lim: self.__find_prime__( lim )
			
		for p in self.prime:
		
			if lim < p: break
			if n % p == 0: return False
			
		return True
		
	def __find_prime__( self, n ):
		
		# 2를 제외한 소수는 홀수이다.
		prime_candidate = self.prime[-1] + 2
		
		while prime_candidate <= n:
		
			if self.is_prime( prime_candidate ):
			
				self.prime.append( prime_candidate )
			
			prime_candidate += 2
		
		return None

p = Prime()
print p.is_prime( 137 )

Algorithm

[파이썬] 재귀함수를 통한 피보나치 수의 구현

루껍 2022. 8. 25. 17:24

피보나치 수

- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

※ 편의상 0번째 항을 0으로 두기도 함.

예시)

1) 반복문을 통한 팩토리얼의 구현

# 반복문을 통한 피보나치 수 구현

# 입력부
n = int(input())

# 0번째, 1번째 피보나치 수를 포함하는 배열 생성
answer_arr = [0, 1]

# 반복문을 통해 n을 입력받았을 때, 기존 배열에 n번째 피보나치 수까지 추가 
for i in range(n-1):
    
    answer_arr.append(answer_arr[1+i] + answer_arr[i])


# 입력받은 n번째 피보나치 수 출력
print(answer_arr[n])

n = 4인 경우의 출력결과 (4번째 피보나치 수)

2) 재귀함수를 통한 팩토리얼의 구현

# 재귀함수를 통한 피보나치 수 구현

def Fibonacci(n):
    
# 0번째 피보나치 수는 0임을 밝힘과 동시에 재귀함수 탈출의 기능
    if n == 0:
        return 0
    
# 1번째 피보나치 수는 1임을 밝힘과 동시에 재귀함수 탈출의 기능
    elif n == 1:
        return 1
    
    else:
        value = Fibonacci(n-1) + Fibonacci(n-2)
        return value

# 입력부
n = int(input())

# 입력받은 n번째 피보나치 수 출력
answer = Fibonacci(n)
print('{0}번째 피보나치 수는 {1} 입니다.'.format(n, answer))

n = 4인 경우의 출력결과 (4번째 피보나치 수)

n = 4인 경우의 재귀함수 모식도

피보나치 수 구현의 경우, 반복문을 사용함으로써 구현 가능하지만,

재귀함수로 피보나치 수를 구현해봄으로써, 재귀함수의 작동에 대해서 공부할 수 있습니다.

재귀함수의 경우에 자연과학 연구, 특정 문제의 모든 경우의 수를 효율적으로 확인하는 백트래킹 메서드(back tracking method), 코딩 테스트 등, 다방면에서 사용되니 작동방법을 명확히 아는 것이 중요하겠습니다.

[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬

주어진 수 N이 소수인지 판단하는 가장 단순한 방법은, 2부터 N-1 까지 모든 수를 순회하면서 이 중 N의 약수가 있는지 확인하는 것이다.

N 이 합성수라면 N = p x q 이고, p <= N ^ 0.5 && q >= N ^ 0.5 이다.

그러므로 N-1 까지 순회하지 않고 N ^ 0.5 까지 순회하도록 최적화 할 수 있다.

그리고 2 보다 큰 모든 짝수는 2 를 약수로 가지고 있으므로, 짝수 중 2 와 홀수들만 소수가 될 수 있다.

# O(N ** 0.5) 시간에 동작하는 소수 판별 알고리즘

def isPrime(N):
    if (N <= 1):
        return False
    if (N <= 2):
        return True

    # 2의 배수 (짝수) 제외
    if not (N % 2):
        return False

    # 합성수 N = p * q 일 때, p <= (N ** 0.5) && q >= (N ** 0.5) 이므로,
    # ( N ** 0.5 ) 까지 순회하는 것으로 합성수 판별이 가능하다.
    sqrtn = int(N ** 0.5)

    # 3이상의 홀수로 나누어 판별, 짝수를 제외한 경우에 대해서 판별
    for div in range(3, sqrtn+1, 2):
        if not (N % div):
            return False
    return True


print(isPrime(14))

파이썬 소수판별 알고리즘 Python 소수 구하기