c++ - Efficient Prime Factorization for large numbers -

c++ - Efficient Prime Factorization for large numbers -

i've been working on little problem need compute 18-digit numbers respective prime factorization. compiles , runs fine, considering works, looking cut down run time of prime factorization. have implemented recursion , threading think might need help in understanding possible algorithms big number computation.

every time run on 4 numbers have pre-made, takes 10 seconds. cut down perchance 0.06 seconds if there ideas out there.

i noticed few algorithms sieve of eratosthenes , producing list of prime numbers prior computing. i'm wondering if elaborate on it. instance, i'm having issues understanding how implement sieve of eratosthenes programme or if idea. , pointers on how approach improve helpful!

here code:

#include <iostream> #include <thread> #include <vector> #include <chrono> using namespace std; using namespace std::chrono; vector<thread> threads; vector<long long> inputvector; bool developer = false; vector<unsigned long long> factor_base; vector<long long> primevector; class primenumber { long long initvalue; // number beingness prime factored vector<long long> factors; // of factor values public: void setinitvalue(long long n) { initvalue = n; } void addtovector(long long m) { factors.push_back(m); } void setvector(vector<long long> m) { factors = m; } long long getinitvalue() { homecoming initvalue; } vector<long long> getvector() { homecoming factors; } }; vector<primenumber> primes; // find primes recursively , have them returned in vectors vector<long long> getprimes(long long n, vector<long long> vec) { double sqrt_of_n = sqrt(n); (int = 2; <= sqrt_of_n; i++) { if (n % == 0) { homecoming vec.push_back(i), getprimes(n / i, vec); //cause recursion } } // pick lastly prime factorization number vec.push_back(n); //return finished vector homecoming vec; } void getuserinput() { long long input = -1; cout << "enter of numbers find prime factors. come in 0 compute" << endl; { cin >> input; if (input == 0) { break; } inputvector.push_back(input); } while (input != 0); } int main() { vector<long long> temp1; // empty vector vector<long long> result1; // temp vector if (developer == false) { getuserinput(); } else { cout << "developer mode active" << endl; long long a1 = 771895004973090566; long long b1 = 788380500764597944; long long a2 = 100020000004324000; long long b2 = 200023423420000000; inputvector.push_back(a1); inputvector.push_back(b2); inputvector.push_back(b1); inputvector.push_back(a2); } high_resolution_clock::time_point time1 = high_resolution_clock::now(); // give each thread number comput within recursive function (int = 0; < inputvector.size(); i++) { primenumber prime; prime.setinitvalue(inputvector.at(i)); threads.push_back(thread([&]{ prime.setvector(result1 = getprimes(inputvector.at(i), temp1)); primes.push_back(prime); })); } // allow of threads bring together together. (auto& th : threads) { cout << th.get_id() << endl; th.join(); } high_resolution_clock::time_point time2 = high_resolution_clock::now(); // print of info (int = 0; < primes.size(); i++) { vector<long long> temp = primes.at(i).getvector(); (int m = 0; m < temp.size(); m++) { cout << temp.at(m) << " "; } cout << endl; } cout << endl; // running time auto duration = duration_cast<microseconds>(time2 - time1).count(); cout << "duration: " << (duration / 1000000.0) << endl; homecoming 0; }

trial partition suitable factoring little numbers. n 2^64, you'll need improve algorithm: recommend starting wheel factorization little factors, followed pollard's rho algorithm rest. trial partition o(sqrt(n)), rho o(sqrt(sqrt(n))), it's much faster. 2^64, sqrt(n) = 2^32, sqrt(sqrt(n)) = 2^16, huge improvement. should expect factor numbers in few milliseconds, @ most.

i don't have c++ code factoring, have readable python code. allow me know if want me post it. if want know more wheel factorization , rho algorithm, have lots of prime number stuff @ my blog.

c++ multithreading algorithm primes prime-factoring