We're a community of 1076K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,075,874 Members — Technology Publication meets Social Media

# Project Euler Problem 3? Beginner

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;
}
}
}``````
7
Contributors
10
Replies
1 Year
Discussion Span
7 Months Ago
Last Updated
13
Views
blee93
Newbie Poster
24 posts since Jul 2010
Reputation Points: 10
Skill Endorsements: 0

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.

arkoenig
Master Poster
711 posts since Jun 2010
Reputation Points: 396
Skill Endorsements: 7

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.

blee93
Newbie Poster
24 posts since Jul 2010
Reputation Points: 10
Skill Endorsements: 0

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

arkoenig
Master Poster
711 posts since Jun 2010
Reputation Points: 396
Skill Endorsements: 7

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.

blee93
Newbie Poster
24 posts since Jul 2010
Reputation Points: 10
Skill Endorsements: 0

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';

arkoenig
Master Poster
711 posts since Jun 2010
Reputation Points: 396
Skill Endorsements: 7

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

jkoske
Newbie Poster
23 posts since Feb 2011
Reputation Points: 9
Skill Endorsements: 0

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

taylorc8
Newbie Poster
12 posts since Nov 2009
Reputation Points: 10
Skill Endorsements: 0

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.

firstPerson
Industrious Poster
4,044 posts since Dec 2008
Reputation Points: 851
Skill Endorsements: 15

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

largest prime factor of 86=43.

frogboy77
Posting Pro in Training
481 posts since Aug 2010
Reputation Points: 100
Skill Endorsements: 1

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;
}
``````
vCillusion
Newbie Poster
1 post since Oct 2012
Reputation Points: 0