77 lines
2.0 KiB
Python
77 lines
2.0 KiB
Python
import math
|
|
|
|
def primes_up_to(n: int):
|
|
"""Generate all primes ≤ n using sieve of Eratosthenes."""
|
|
if n < 2:
|
|
return []
|
|
sieve = [True] * (n + 1)
|
|
sieve[0] = sieve[1] = False
|
|
for p in range(2, int(math.isqrt(n)) + 1):
|
|
if sieve[p]:
|
|
step = p
|
|
start = p * p
|
|
sieve[start:n + 1:step] = [False] * ((n - start) // step + 1)
|
|
return [i for i, is_p in enumerate(sieve) if is_p]
|
|
|
|
def factor_exponents(n: int):
|
|
"""Return dict {prime: exponent} for n (n ≥ 1)."""
|
|
exps = {}
|
|
if n <= 1:
|
|
return exps
|
|
limit = math.isqrt(n)
|
|
for p in primes_up_to(limit):
|
|
if p * p > n:
|
|
break
|
|
while n % p == 0:
|
|
exps[p] = exps.get(p, 0) + 1
|
|
n //= p
|
|
if n > 1: # leftover prime
|
|
exps[n] = exps.get(n, 0) + 1
|
|
return exps
|
|
|
|
def exponents_in_prime_order(n: int, min_len=7):
|
|
"""
|
|
Produce exponents in order [2, 3, 5, 7, 11, 13, ...],
|
|
padded with zeros to length >= min_len.
|
|
"""
|
|
if n == 1:
|
|
return [0] * min_len
|
|
|
|
exps = factor_exponents(n)
|
|
|
|
# generate primes in ascending order until we cover all factors
|
|
primes_needed = sorted(exps.keys())
|
|
max_prime = max(primes_needed) if primes_needed else 2
|
|
primes_list = primes_up_to(max_prime)
|
|
|
|
out = [exps.get(p, 0) for p in primes_list]
|
|
|
|
# pad with zeros
|
|
while len(out) < min_len:
|
|
out.append(0)
|
|
|
|
return out
|
|
|
|
def format_exponents(exps):
|
|
"""Format as comma-separated list with zero-padded width=3."""
|
|
return ",".join(f"{e:03d}" for e in exps)
|
|
|
|
def main():
|
|
for s in range(1,100):
|
|
#s = input("Enter a positive integer (1..10000000): ").strip()
|
|
try:
|
|
n = int(s)
|
|
except ValueError:
|
|
print("Error: please enter an integer.")
|
|
return
|
|
if n < 1 or n > 10_000_000:
|
|
print("Error: number must be between 1 and 10,000,000.")
|
|
return
|
|
|
|
exps = exponents_in_prime_order(n, min_len=7)
|
|
print(s, ': ',format_exponents(exps))
|
|
|
|
if __name__ == "__main__":
|
|
main()
|
|
|