### trying to reduce the overhead on my program that is supposed to find the highest prime of 600851475143

Pages: 12
maybe different gcc's are giving different outputs??
> maybe different gcc's are giving different outputs??

No. They seem to agree.

74:
http://ideone.com/EyOa8e
http://ideone.com/txWxLS

161:
http://ideone.com/GxDpmr
http://ideone.com/LxRKPG

The problem with 74 can be fixed by first checking if the number is even.
The problem with 161 can be fixed with a `break` after printing the first value.

you don't have to get the primes to 'prime' factorize a number...

 ``1234567891011121314151617181920212223242526`` ``````#include #include typedef unsigned long long ulong; void print_prime_factors(ulong n) { std::cout << n << ": "; if (!n) { std::cout << "0 is not a composite number.\n"; return; } ulong sqrt_n = sqrt(n); for (ulong i=2; i<=sqrt_n && n!=1; ++i) { if (n%i==0) { std::cout << i << " "; } while (n%i==0) { n /= i; } //get rid of the exponents } if (n != 1) { std::cout << n; } //now n is a prime, must output it! std::cout << "\n"; } int main() { ulong n; while (std::cin >> n) { print_prime_factors(n); } }``````

http://ideone.com/G2PS4Q

a (slighty) faster way would check if 2 is divisor, then start from i=3 to square root n inclusive, check if i is divisor, then add 2 to i (only check for odd i)

another (slighty) faster way would check for i=2, i=3, then start from i=5 to square root n inclusive, check if i and i+2 is/are divisor(s), then add 6 to i (only check for i = 6k-1 and i=6k+1)

and more faster if square root n is re-calculated everytime we find a divisor...

An Python implementation: http://ideone.com/nuiQAP
Last edited on
This is the way i did it :)

 ``123456789101112131415161718192021222324252627282930313233`` ``````#include #include using namespace std; int main() { unsigned long long n = 600851475143ULL; //not even, so 2 wont be a factor bool prime; int n2 = sqrt(n); for(int i = n2; i > 3; i--) { prime = 1; if(n%i == 0) { if(i % 2 != 0) { for(int j = 2; j < i; j++) { if(i % j == 0) prime = false; } } if(prime && (n%i == 0)) { cout << i << endl; break; } } } }``````

it was pretty quick
Topic archived. No new replies allowed.
Pages: 12