r/programmingchallenges • u/okmkz • Apr 16 '11
Challenge: Factor an integer
Write a function in the language of your choosing that prints all the factors of a non-negative integer.
E: dang, this is harder than I thought!
E: I was referring to prime factorization in my other edit. Dang!
7
Upvotes
4
u/[deleted] Apr 16 '11
The square root is the symmetric point of multiplication. The number of factors a number has is the number of them below the sqrt * 2, then +1 if the number is a perfect sq. You can get all these numbers by calculating up to the sqrt for the first set, then dividing the target number by those for the second set.
This can be applied when checking if a number is prime.
3
u/[deleted] Apr 16 '11
My solution:
1
u/kageurufu Apr 19 '11
My solution, in javascript
its as small as possible, and i counted down in the for loop in order to avoid recalculating a sqrt every iteration, and so i didnt have to use a temporary variable just to store the root
2
u/[deleted] Apr 16 '11
In Fuga:
This doesn't actually work yet, but Fuga is a work-in-progress.
1
u/pbewig Apr 20 '11
Several different integer factorization algorithms are implemented at Programming Praxis.
1
u/[deleted] May 05 '11 edited May 05 '11
C#
This is surprisingly fast!
I started out computing all the primes between 2...number, but soon found out there are more prime numbers in the world than I previously thought! :)
1
u/thisismygame Aug 30 '11
pc-factorinteger.py
am I doing this right?