Efficient algorithm for finding large prime factors
Ok so I kind of went all brute force with this problem, and it takes forever to find a result. I was wondering what all good algorithms and/or tricks there are to finding large prime factors
Thanks for the link, but I am having a hell of a time finding the largest prime factor of a number. Is this generally a hard task?
12 decimal digits for this number. It's project Euler number 3. I've had a few ideas as to how to do it, but none seem very efficient
That should be trivial. (It can be held in a std::uint_fast64_t).
In a loop,
1. Divide the numbers by prime numbers 2, 3, 5, 7, ...
2. Check if the result is of the form 6n-1 or 6n+1 ( all prime numbers greater than 3 are of the form 6n-1 or 6n+1)
3. If it is, perform a deterministic Miller-Rabin primality test on it.
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
In a loop,
1. Divide the numbers by prime numbers 2, 3, 5, 7, ...
2. Check if the result is of the form 6n-1 or 6n+1 ( all prime numbers greater than 3 are of the form 6n-1 or 6n+1)
3. If it is, perform a deterministic Miller-Rabin primality test on it.
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
Topic archived. No new replies allowed.