Rosetta Code

Prime decomposition

Find the prime factors of composite integers with trial division.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/prime_decomposition.vibe
type RunResult = {
  sample_composite: array<int>,
  thousand_twenty_three_times_thousand_twenty_four: array<int>,
  twelve: array<int>
}

def prime_decomposition(number: int) -> array<int>
  factors: array<int> = []
  remaining = number

  while remaining % 2 == 0
    factors.push(2)
    remaining = remaining // 2
  end

  candidate = 3
  while candidate * candidate <= remaining
    while remaining % candidate == 0
      factors.push(candidate)
      remaining = remaining // candidate
    end
    candidate = candidate + 2
  end

  if remaining > 1
    factors.push(remaining)
  end

  factors
end

def run -> RunResult
  {
    twelve: prime_decomposition(12),
    thousand_twenty_three_times_thousand_twenty_four: prime_decomposition(1023 * 1024),
    sample_composite: prime_decomposition(2 * 3 * 5 * 7 * 11 * 11 * 13 * 17)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.