Created
July 13, 2011 11:47
-
-
Save Envek/1080156 to your computer and use it in GitHub Desktop.
Calculate maximum prime multiplier of number
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <inttypes.h> | |
#include <math.h> | |
using namespace std; | |
uint64_t maxPrimeMul (uint64_t num); | |
bool isPrime (uint64_t num); | |
int main () { | |
uint64_t num; // = 600851475143; | |
cin >> num; | |
uint64_t mul = maxPrimeMul(num); | |
cout << mul << endl; | |
return 0; | |
} | |
// Search for maximum prime multiplier of number | |
uint64_t maxPrimeMul (uint64_t num) { | |
// In the case if num is prime number itself… | |
if (isPrime(num)) | |
return num; // Yes, it's the answer! | |
// Otherwise, we need to search for it | |
uint64_t top = num/2, max = 1; | |
for (uint64_t i = 1; i < top; i++) { | |
if (isPrime(i) && !(num%i)) { | |
max = i; | |
cerr << "POSSIBLE: " << i << endl; // Uncomment for debug purposes | |
} | |
} | |
return max; | |
} // Thank you for your patience | |
// Check number to be a prime one | |
bool isPrime (uint64_t num) { | |
if ( !(num%2) ) | |
return false; | |
uint64_t top = (uint64_t) sqrt((double)num); | |
for (uint64_t i = 3; i <= top; i += 2) { | |
if ( !(num%i) ) | |
return false; | |
} | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment