본문 바로가기

소수

(15)
[Python] 십진수소수 이진수로 변환하기 십진수 정수를 이진수로 변환하는 것은 파이썬이 기본으로 제공하는 bin 함수를 사용하면 된다. 소수점 이하 자릿수를 포함한 십진수를 이진수로 표현하는 함수를 만들어 보았다. 입력을 float 으로 변환하면, 부동소수점 오류로 정확한 계산이 불가능하다. 분수를 다룰 수 있는 fractions 모듈을 이용하여 정확하게 소수점 아래까지 구할 수 있다. 순환마디까지 구할 수 있는데, 일단 무시하고 30자리까지 구하는 걸 구현했다. from fractions import Fraction def conv2bin(s): x = Fraction(s) x1 = x//1 x2 = x - x1 digits = [] tail = "..." for _ in range(30): if x2 == 0: tail = "" break ..
SwiftUI : Primes Numbers 아주 간단하게 최초 100개의 소수를 구하는 swiftui 프로그램. 최초에 2 이상인 100개의 정수가 화면에 나열됨. 각 숫자 버튼을 누르면, 누른 숫자의 배수들을 제거함. 2부터 하나씩 버튼을 눌르면, 남아있는 숫자들이 소수들. import SwiftUI struct ContentView: View { @State private var primes = Array(2...30000) @State private var clicked = Set() var body: some View { VStack { ForEach(0..
[Swift] 소인수분해 swift 로 소인수분해하는 코드를 짜 봤다. 정수를 인자로 주면, 그 정수의 소인수분해를 (소수, 거듭제곱수) 의 어레이로 반환한다. 1은 빈 어레이를 반환한다. #!/usr/bin/env swift import Foundation func primeFactors0(_ n: Int) -> [(Int, Int)] { var factors: [(Int, Int)] = [] var p = 2 var pow = 0 var n = n while p * p 0 { factors.append((p, pow)) } p += 1 pow = 0 } if n != 1 { factors.append((n, 1)) } return factors } func primeFactors(_ n: Int) -> [(Int, Int)]..
[EP 047] 소인수분해의 소수의 갯수가 4개 문제는 이렇다. 644는 소인수분해하였을 때, 22 x 7 x 23 으로 세 개의 서로다른 소수로 이루어진다. n, n+1, n+2, n+3 이 모두 네 개의 서로다른 소수로 이루어지는 최소의 n을 구하라. 1부터 차례대로 소인수분해를 해 나가야 하기 때문에, 완전한 소수의 리스트를 관리할 수 있다. 소수판정이 매우 효율적이라서 기쁘다. 또한 소인수분해를 기록하는 리스트도 기록해 나가는데, 일단 하나의 소수만 발견하면 기록된 리스트를 이용해서 매우 효율적으로 원하는 값을 구할 수 있다. 소스를 봐라. # Author : DwYoon # PROJECT EULER # http://projecteuler.net/index.php?section=problems&id=47 # PROBLEM 47 import ti..
[Python] 분수의 무제한 소수표현 구하기 분수의 십진수 소수 표현을 자릿수 제한없이 구하는 함수. from typing import List, Tuple def get_div_decimals(n: int, m: int = 1, limit: int = 0) -> Tuple[int, List[int], List[int]]: q = m // n m = (m % n) * 10 dividend = m dividend_list = [] digit_list = [] while True: # print(digit_lst) if dividend in dividend_list: break dividend_list.append(dividend) digit = dividend // n dividend = (dividend % n) * 10 digit_list.app..
[EP0010] 백만이하 소수의 합 특정 수 이하의 모든 소수를 구하는 알고리즘을 비교해 보았다. gen_primes 는 스택오버플로우에서 검색하여 발견한 방법. 에라토스테네스의 방법이 특정수 이하까지의 체를 만들기 위해 메모리를 잡아야 하는 단점이 있는데, 메모리를 덜 잡고 하는 방법이라고 한다. 이해를 하려면 좀 더 들여다 봐야하겠으나, 내 방법보다 훨씬 빠르게 나왔다. (무식하게 메모리 잡고 하는 방법보다는 약간 느렸지만) 커멘트로 써 놓은 테스트 결과는 천만으로 한 것. 백만일 때의 결과는 각각 3.1초, 3.3초, 1.3초, 1.5초. import time import functools from tqdm import tqdm def log_elapsed(func): @functools.wraps(func) def newfunc(*..
[EP003] 큰 수의 소수분해 from typing import List import math from time import time from tqdm import tqdm def get_primes_under_siev(n: int) -> List[int]: root_n = int(math.sqrt(n)) siev = {} siev[0] = siev[1] = 0 siev[2] = 1 for i in range(2, root_n + 1): # print(i) if siev.get(i, 1): for j in range(i + i, n + 1, i): siev[j] = 0 # print(siev) primes = [n for n in range(2, n + 1) if siev.get(n, 1)] return primes def facto..
[EP 050] 연속된소수의합이 다시 소수 무식한 방법으로 푼다. 루프를 빠져나오는 조건을 잘 줘야 빨리 끝난다. 소수를 구할 때, 나눌 수가 소수후보의 제곱근보다 크다면 빠져나오라는 조건을 빼면 시간이 하염없이 걸리고, 연속된소수의 합이 다시 소수인 모든 수를 구하는 것이 아니고, 그 소수 갯수의 최대값을 구한다는 조건을 for 루프에 잘 적용하면 또 시간을 더 단축할 수 있다. 물론 깔끔함은 훼손되지. /* * http://projecteuler.net/index.php?section=problems&id=50 Problem 50 15 August 2003 The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is t..