/* * Created by Mohammad Amin Chitgarha. * It has hints on the output and in the code. * So, no more comments! :) * Just run it! */ #include #include #include using namespace std; // Global variables for my pattern int oneDigitPrimes[4] = {2, 3, 5, 7}, primePattern[8] = {2, 4, 2, 4, 6, 2, 6, 4}; // Declare functions template void get_divs(T n, T minDiv, T pLevel); template void get_divisors(T n); template T random_number(int min, T max); int main() { // Initialize variables int start, end; long long num; while (true) { // Get the number cout << "Enter a number (0 for a random one or a string to exit): "; cin >> num; if (!cin.good()) break; // If there isn't a proper input, choose a number randomly if (num == 0) { num = abs(random_number(1, (long long) pow(10, 15))); cout << "Random number is " << num << "." << endl << endl; } for (int i = 0; i < 2; i++) { // Which algorithm is? cout << "- " << (i == 0 ? "My algorithm" : "Regular one") << ":" << endl << "Prime factors: "; // Record the execution time start = clock(); /* * Comparison between my algorithm and the regular one. * No differences, except in execution time (on many big number)! */ if (i == 0) get_divs(num, (long long int) 2, (long long int) 7); else get_divisors(num); // Record the execution time end = clock(); // Print the execution time double calculationTime = (end - start) / double(CLOCKS_PER_SEC); cout << endl << "Calculated in "; if (calculationTime != 0) cout << calculationTime << " second(s)."; else cout << "less than a millisecond."; cout << endl; } cout << endl; } // :) cout << "Hope you enjoyed;" << endl; cout << "Tell me the bugs and your suggestions! ;)"; return 0; } /* * Find prime factors of a number, using my own algorithm. * The algorithm is about two-three times faster than the regular algorithm. * I can't explain it in English, find how it works (it's not easy to find)! * As I tested, its performance does not depends on number bigness. */ template void get_divs(T n, T minDiv, T pLevel) { if (pLevel == 7) for (int i : oneDigitPrimes) if (n % i == 0) { while (n % i == 0) { cout << i << ", "; n /= i; } if (n != 1) get_divs(n, (T) i, (T) 7); return; } T squareRoot = (T) sqrt(n), i = pLevel == 7 ? 7 : minDiv; for (T j = pLevel; i <= squareRoot; j++) { i += primePattern[j % 8]; if (n % i == 0) { while (n % i == 0) { cout << i << ", "; n /= i; } get_divs(n, i, ++j); return; } } cout << n; } // Regular algorithm to find prime factors template void get_divisors(T n) { T squareRoot = (T) sqrt(n); for (T i = 2; i <= squareRoot; i++) if (n % i == 0) { cout << i << ", "; get_divisors(n / i); return; } cout << n; } // Generates a random number template T random_number(int min, T max) { mt19937 mt_rand(time(nullptr)); T x = mt_rand(), y = mt_rand(); return ((x * y) % (max - min + 1)) + min; }

Prime factorization, with a faster algo