Is there an efficient way to find all the divisors of a number that leave no remainder? And by efficient, I don't mean dividing a number by every other number to see if the remainder is zero.
Printable View
Is there an efficient way to find all the divisors of a number that leave no remainder? And by efficient, I don't mean dividing a number by every other number to see if the remainder is zero.
I could be wrong but I don't think there are easy solutions for this, not for big numbers anyway.
If you had a list of all prime numbers up to N, then you could use that list to determine the factors of numbers up to N², this would be more efficient than testing with every number.
You could write a variant of the Sieve of Eratosthenes where rather than just marking composites you log the prime factors.
Check out...
Rational sieve
Special number field sieve
General number field sieve
The latter two made my little brain hurt
If there was a truly easy method to find this other than a brute force approach, then modern computer security would become garbage, since it is based on the very difficulty of factoring large numbers even for powerful computers.
Ehehe... no. But you can loop through them, too! :)
Code:Dim factors As New List(Of Integer)
If numbertofactor = 0 Then Exit Sub
For i As Integer = 0 To (numbertofactor \ 2) + 1
If (numbertofactor Mod i) = 0 Then factors.Add(i)
Next