# 테페리넷

### 사이트 도구

ps:teflib:numtheory_old

# (old) numtheory.py

## linear_congruences v1.0

### 코드

# N linear_congruences
# I {"version": "1.0", "typing": ["Iterable"]}
def linear_congruences(a: Iterable[int], m: Iterable[int]) -> int:
"""Returns a solution of the given system of linear congruences.

This function finds the smallest non-negative integer x that satisfies the
following simultaneous linear congruence equations:
x % m_0 = a_0
x % m_1 = a_1
...
x % m_n = a_n   (All m_i values must be co-prime.)

Note that any number x_k = x + k*(a_0*a_1*...*a_n) can also be the solution.
"""
prod = 1
for m_i in m:
prod *= m_i
return sum((p := prod // m_i) * pow(p, -1, m_i) * a_i
for a_i, m_i in zip(a, m)) % prod

## prime_list v1.0

### 코드

# N prime_list
# I {"version": "1.0", "typing": ["List"], "import": ["math"]}
def prime_list(limit: int) -> List[int]:
"""Returns a list of prime numbers up to the given integer."""
if limit < 3:
return [2] if limit == 2 else []
size = (limit - 3) // 2
is_prime = [True] * (size + 1)
for i in range(math.isqrt(limit - 3) // 2 + 1):
if is_prime[i]:
p = i + i + 3
s = p * (i + 1) + i
is_prime[s::p] = [False] * ((size - s) // p + 1)
return [2] + [i + i + 3 for i, v in enumerate(is_prime) if v]

## prime_list v1.22

### 코드

# N prime_list
# I {"version": "1.22", "import": ["math"]}
def prime_list(a: int, b: int = -1) -> list[int]:
"""Returns a list of prime numbers in the given range, [1, a] or [a, b]."""
start, limit = (1, a) if b == -1 else (min(a, b), max(a, b))
if limit < 3:
return [2] if limit == 2 else []
size = (limit - 3) // 2
is_prime = [True] * (size + 1)
for i in range(math.isqrt(limit - 3) // 2 + 1):
if is_prime[i]:
p = i + i + 3
s = p * (i + 1) + i
is_prime[s::p] = [False] * ((size - s) // p + 1)
start_pos = 0 if start == 1 else (start - 2) // 2
s = start_pos * 2 + 3
ans = [] if start > 2 else [2]
return ans + [i + i + s for i, v in enumerate(is_prime[start_pos:]) if v]

## 토론

댓글을 입력하세요:
D O T Q​ Q

ps/teflib/numtheory_old.txt · 마지막으로 수정됨: 2022/07/23 02:59 저자 teferi