Skip to content

Instantly share code, notes, and snippets.

@Envek
Created July 13, 2011 11:47
Show Gist options
  • Save Envek/1080156 to your computer and use it in GitHub Desktop.
Save Envek/1080156 to your computer and use it in GitHub Desktop.
Calculate maximum prime multiplier of number
#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