23
1
In this task, you have to write a program, that computes the prime factors of a number. The input is a natural number 1 < n < 2^32. The output is a list of the prime factors of the number in the following format. Exponents must be omitted if they are 1. Only output prime numbers. (Assuming the input is 131784):
131784 = 2^3 * 3 * 17^2 * 19
Using the same amount of whitespace is not required; whitespace may be inserted wherever appropriate. Your program should complete in less then 10 minutes for any input. The program with the shortest amount of characters wins.
@IngoBürk I think CJam was invented after this challenge was posted, disqualifying it. – FUZxxl – 2015-02-08T16:06:04.623
@IngoBürk 18 chars:
rimF{1-'^*}%" * "*
and indeed it doesn't qualify – aditsu quit because SE is EVIL – 2015-02-10T16:14:36.7309Bonus points if your program can factor 6857599914349403977654744967172758179904114264612947326127169976133296980951450542789808884504301075550786464802304019795402754670660318614966266413770127 in less than 73 days! – Joey Adams – 2011-04-07T02:08:39.683
@Joey Adams: The factorization starts out with 1771113997313597... – FUZxxl – 2011-04-09T15:48:13.550
3
@FUZxxl: I think you made a mistake copying the number. It's the product of two large primes.
– Joey Adams – 2011-04-09T17:50:51.247@Joey Can we use Shor's Algorithm? – Mateen Ulhaq – 2011-05-03T03:30:28.623
@muntoo: Do you have the hardware to test it? :-) – Joey Adams – 2011-05-03T05:42:59.820
23@Joey I accidentally spilled some coffee over my quantum computer, and my friend is using his to "hack into the US Government" or something unimportant, so, no. :( – Mateen Ulhaq – 2011-05-03T05:59:53.873
What, no CJam yet? – Ingo Bürk – 2014-11-01T07:22:24.173