Project Euler Problem 3? Beginner

[blee93]

I am doing Project Euler Problem 3, but I seem to get stuck. I have written some code that makes sense (at least to me) but keeps printing the answer to 137.

This is the problem:
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

#include <iostream>
#include <cmath>

using namespace std;

bool isprime(int);
int calcprime(int);

int main()
{
    int number = sqrt(600851475143);
    int biggestprime = calcprime(number);
    cout << "The biggest prime is: " << biggestprime << endl;
}

bool isprime(int number)
{
    for (int i = 2; i <= sqrt(number); i++)
    {
        if (number % i == 0)
            return false;
    }
    return true;
}

int calcprime(int number)
{
    for (int i = number; i > 2; i--)
    {
        if ((number % i == 0) && (isprime(i)))
        {
            return i;
        }
    }
}

[arkoenig]

Not every C++ implementation is capable of supporting an integer as large as 600851475143. So if you want to use a C++ implementation that doesn't support integers that large, you have a few choices:

1) Figure out how to represent such large integers for yourself.

2) Find an extended-precision integer arithmetic package and use it.

3) Do your computations in floating-point. This may sound like a surprising approach, but it's workable if you're careful.

[blee93]

I know that the long long type works for the number, but when I change all my ints to long long's, it never finishes running (don't really know why, maybe it's taking too long). So I took the sqrt of the number instead because that would be the biggest number divisible by that large number (besides the large number itself).

Not sure why this program always ends up with 137, though.

[arkoenig]

How many times do you expect the loop in lines 28-34 to execute?

[blee93]

Not sure how many times it'll execute. I think (int)(sqrt(600851475143)) - 2 times?

For the answer, I don't know why I keep getting 137.
The real answer, which I forgot to mention, is 6857.

[arkoenig]

The trouble is that unless you've verified that an int is capable of containing the value 600851475143, I don't see how you can count on the results.

What happens if you execute this on your implementation?

cout << 600851475143 << '\n';

[jkoske]

This is just a guess, but I think you may have a logic error in that if you are looking for the largest prime factor you should do the upper half of the possible factors. You are decrementing from sqrt(bignum) to 2. You should be decrementing from bignum to sqrt(bignum).

[taylorc8]

Please check to make sure std::numeric_limits<unsigned long long>::max() > 600851475143

[mrnutty]

Integer range : –2,147,483,648 to 2,147,483,647
unsigned integer range : 0 to 4,294,967,295
unsigned long long range : 0 to 18,446,744,073,709,551,615

so a integer cannot go up to 600851475143, so use long long type.

Also I would suggest for you to start from the number 600851475143 - 2 and go on from there. It will be faster.

[frogboy77]

sqrt(86)=9.2736.........

largest prime factor of 86=43.

[vCillusion]

Possible solution

Proceed in such a manner for long numbers I waited for 25 minutes but this solves the problem ;)

#include<stdio.h>
#include<string>
#include<iostream>
#include<math.h>
int prime(unsigned long long);
using namespace std;
int main(){
unsigned long long ii, ij;
unsigned long long in;
cin>>in;
ij = ceil(in/2);
if( (ij % 2) == 0 )
ij -= 1;
for(ii = 3 ;ii < ij;ii += 2){
    if(in % ii == 0){
        if(prime(ii) == 1 ){
            cout<<" ans "<<ii<<endl;
        }
    }
}
return 0;
}
int prime(unsigned long long ii){
        unsigned long long ij;
        for(ij = 3;ij < ii/2 ;ij += 2){
            if( (ii % ij) ==0){
                return 0;
            }
        }
        return 1;
}