fork download
copy 
  1. # your code goes here
  2. import math
  3. from collections import defaultdict
  4.  
  5. MAXN = 1000000
  6.  
  7. # Array to store the smallest prime factor for each number
  8. spf = [i for i in range(MAXN + 1)]
  9.  
  10. def compute_spf():
  11.     """Precomputes the Smallest Prime Factor (SPF) for all numbers up to MAXN."""
  12.     for i in range(2, int(math.isqrt(MAXN)) + 1):
  13.         if spf[i] == i:  # i is prime
  14.             for j in range(i * i, MAXN + 1, i):
  15.                 if spf[j] == j:  # Update spf[j] if not already updated
  16.                     spf[j] = i
  17.  
  18. def get_prime_factors(num):
  19.     """Returns a dictionary of prime factors and their powers for a given number."""
  20.     factors = defaultdict(int)
  21.     while num > 1:
  22.         prime = spf[num]
  23.         factors[prime] += 1
  24.         num //= prime
  25.     return factors
  26.  
  27. # --- Example Usage ---
  28. compute_spf()
  29.  
  30. numbers_to_factor = [12, 100, 999999]
  31.  
  32. for num in numbers_to_factor:
  33.     factors = get_prime_factors(num)
  34.     formatted = " * ".join(
  35.         [f"{p}^{count}" if count > 1 else str(p) for p, count in factors.items()]
  36.     )
  37.     print(f"{num} = {formatted}")
Success #stdin #stdout 0.32s 52364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12 = 2^2 * 3
100 = 2^2 * 5^2
999999 = 3^3 * 7 * 11 * 13 * 37
https://ideone.com/EiU94Z
language:
Python 3 (python  3.12)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!