Algorithm
[python] 소인수분해, 최소 공배수 구하기
문제(1) 소인수분해 설명 소인수 분해란 소수가 아닌 합성수를 소수의 곱으로 나타내는 방법을 말한다. (입력된 숫자 n이 i로 나누어지면 해당 i는 n의 인수에 해당하며 n = n//i로 저장하여 이 과정을 반복한다.) 코드 n = int(input("자연수 입력 :")) i = 2 while i
분류 전체보기
Algorithm
[python] 반복문과 재귀 호출을 사용하여 두 수의 최대 공약수 구하기
문제 설명 최대 공약수란 2개의 숫자를 소인수분해한 후에 결과가 중복되는 부분을 찾아 곱셈한 수 12 = 2 * 2* 3 / 18 = 2*3*3 중복된 부분은 2*3으로 최대 공약수는 6이다. 하지만 우리는 유클리드 호제법을 통해 최대 공약수를 구해본다. 예시) 192%72=48 나머지는 48 여기서 다시 72 와 48을 나눈다. 72 % 48=24 다음 과정은 48 % 24 =0 나머지가 0이 되므로 연산을 중지하고 이전에 구한 나머지 24가 192, 72 의 최대 공약수가 된다. 반복문을 통한 코드 def f(a,b): if a > b : pass else : a, b = b, a while b > 0: c = b b = a%b a = c return a n, m = map(int, input("두 ..
Algorithm
[python] 파이썬을 이용해 소수 추출하기 / 에라토스테네스의 체 방법으로 추출하기
문제(1) 설명 2와 입력된 자연수 n 사이의 모든 소수를 출력해보자. 코드 def check_prime(n) : i = 2 while i < n : if n%i==0: break i += 1 if i == n : print(f'{n}은 소수') else : print(f'{n}은 합성수') n = int(input("자연수 하나를 입력하시오 :")) i = 2 while i
Algorithm
[python] 파이썬을 이용해 정수의 약수와 소수 구하기
문제 설명 2부터 N(입력받은 수)까지의 숫자가 소수인지 아닌지를 순서대로 검사하고, 소수라면 소수라는 메시지를 출력하고, 소수가 아니면 해당 숫자의 약수를 구하여 출력하는 프로그램을 만들어보자. (1은 소수가 아니며 2는 소수이다.) 코드 def solve(n): global flag print("{0}은 합성수".format(n)) i = 1 while i
