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

[devonrevenge]

maybe different gcc's are giving different outputs??

[JLBorges]

> 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.

[tntxtnt]

nope. It's in your code.

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

#include <iostream>
#include <cmath>

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

[jidder]

This is the way i did it :)

#include <iostream>
#include<math.h>
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