CODEWITHSUNDEEP
c++
sparite
sparite

Reputation: 23

Project Euler #3 Get largest prime factor of a number

So the Question was as follows:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

I made a code for the question whose logic and algorithm seems correct but I can't seem to find the mistake, there's the code.

#include <iostream>

using namespace std;

int main()
{
    long int x = 600851475143;
    for(long int i=x-1; x%i; --i);
    cout << i;
    return 0;
}

RE: Didn't know about the 'i' scope, Teachers in my school didn't tell me =) [not blaming them]

RE: Thanx for all your responses, I got the answer. =)

Upvotes: 1

Views: 1401

Answers (6)

Himanshu Dutta
Himanshu Dutta

Reputation: 73

Please find one of the solution as below as the previous solution is running in infinite loop for me. Not quite sure though. But the below code works for me:

#include<stdio.h>
#define MAX_NUM 600851475143UL
unsigned long largest_prime_factor(unsigned long num)
{
    unsigned long c = 1;
    while(1)
    {
        for(unsigned long i = 2; i <= num; i++)
        {
            if(num % i == 0)
            {
                c = i;
                num = num / i;
                goto loop;
            }
        }
        break;
    loop:
        continue;
    }
    return c;
}

int main()
{
    printf("%ld", largest_prime_factor(MAX_NUM));

    return 0;
}

Upvotes: 0

πάντα ῥεῖ
πάντα ῥεῖ

Reputation: 1

At least the following code compiles correctly and has no overflow problems:

#include <iostream>

using namespace std;

int main()
{
    unsigned long long x = 600851475143, i;
 // ^^^^^^^^ Note the unsigned!
    for(i= x-1;x%i;--i);
    cout<<i;
    return 0;
}

Upvotes: 0

Karoly Horvath
Karoly Horvath

Reputation: 96266

There's also a bug:

if x is prime, you won't find the answer. i should start from the same value.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726799

There are two small issues and one big issue:

  • Your i variable is out of scope for printing - the scope of variables declared in the header of the statement ends with the statement itself. In this case, i is not visible after the semicolon, so you need to declare it outside the for
  • Your variables may not necessarily hold the values that you want to put into them - long is allowed to be a 32-bit type, and on many platforms, it is. To make it at least a 64-bit type, change the declaration to long long.

Once you fix these problems, your code will compile. However, it will take ages to run because of the third, big, problem with your code: your algorithm is too slow.

Upvotes: 1

Riccardo T.
Riccardo T.

Reputation: 8937

What about this instead? Just declare the i outsude of the for.

int main()
{
  long int x = 600851475143, i;
  for (i = x-1; x%i; --i);
  cout << i;
  return 0;
}

In your version i doesn't exist when you call cout.

int main()
{
    long int x = 600851475143;    /* here i doesn't exist */
    for(long int i=x-1; x%i; --i) /* here i is declared */ ;
    /* the for is closed by ; so the scope of i is already closed */
    cout<<i;
    return 0;
}

However, there are also other problems in your solution as pointed out by other answers and comments.

Upvotes: 0

HadeS
HadeS

Reputation: 2038

i is not accessible outside for loop.

long int i=0;
for(i= x-1;x%i;--i);
cout<<i<<endl;

Upvotes: 0

Related Questions