CODEWITHSUNDEEP
language-agnostic
omega
omega

Reputation: 43893

How to get k prime factors?

Is there an algorithm that can take a number k, and return a number j such that j has k prime factors? Note: the algorithm should run in polynomial time.

Assume you don't have a table of prime numbers.

Upvotes: 0

Views: 230

Answers (1)

Jerry Coffin
Jerry Coffin

Reputation: 490398

Obvious answer: starting from a table of prime numbers, given a number k, multiply k of those prime numbers together and return the result. Assuming k is small enough that the multiplication time remains constant, that should run in linear time.

If you need to count the time to find the prime numbers, it should still be polynomial time, using a sieve of Erathosthenese to find the table of prime numbers.

Upvotes: 4

Related Questions