max long integer not printing?

[RUNNER PRO AGARIO]

I was doing the third exercise of Project Euler, and I don't know what went wrong? Could someone point out the error in my code?

  #include <iostream>
#include <vector>

bool isPrime(long num)
{
    std::vector<long> factors;
    for (long n=1;n<num;n++)
    {
        if (num%n==0)
        {
            factors.push_back(n);
        }
    }
    if (factors.size() > 2)
    {
        return false;
    }
    else return true;
}

int main()
{
  int max = 0;
  long num = 600851475143;
  for (long i=1;i<num;i++)
  {
      if (num%i==0 && i > max)
      {
          if (isPrime(i))
          {
              max=i;
          }
      }
  }
  std::cout << max;
}

Running this, I get the value of 0, but that doesn't make sense whatsoever. What am i doing wrong?

[Chervil]

Try this:

1 2 3 4 5 6 7 8 9 10 11

#include <iostream> int main() { long num1 = 600851475143; long long num2 = 600851475143; std::cout << "num1 = " << num1 << '\n'; std::cout << "num2 = " << num2 << '\n'; }

num1 = -443946297 num2 = 600851475143

Note the compiler warning also,

Line 5 [Warning] overflow in implicit constant conversion [-Woverflow]

[RUNNER PRO AGARIO]

I changed my code to :

#include <iostream>
#include <vector>

bool isPrime(long num)
{
    std::vector<long> factors;
    for (long n=1;n<num;n++)
    {
        if (num%n==0)
        {
            factors.push_back(n);
        }
    }
    if (factors.size() > 2)
    {
        return false;
    }
    else return true;
}

int main()
{
  long max = 0;
  long num = 600851475143;
  for (long i=1;i<num;i++)
  {
      if (num%i==0 && i > max)
      {
          if (isPrime(i))
          {
              max=i;
          }
      }
  }
  std::cout << max;
}

yet i still get 0 or no output in the console window. Any ideas?

[dhayden]

In addition to what Chervil says, let's look at that loop:

  long num = 600851475143;
  for (long i=1;i<num;i++)

The loop will run 600 BILLION times. If each iteration takes just one nanosecond, the program will run for 600 seconds, which is 10 minutes.

Clearly you'll need a faster algorithm. You may want to start by getting the code working for a smaller value of num. Then think of ways to speed up the process.

[RUNNER PRO AGARIO]

ooooooooooooohhhh no wonder i waited so long. Ok i will try

[dhayden]

I just wrote a solution that runs on a slow sparc system in less than 1 millisecond, so there's definitely room for improvement :).

[RUNNER PRO AGARIO]

wow.

[Naughty Albatross]

So long is nolonger an int now?

In the past, long == int

Is it true or am I wrong?

[Naughty Albatross]

@RUNNER PRO AGARIO
Why being a masochist?

Why not make your program a little more active?

==>

#include <iostream>
#include <vector>
bool isPrime(long long num)
{
    std::vector<long long> factors;
    for (long long n=1;n<num;n++)
    {
        if (num%n==0)
        {
            factors.push_back(n);
        }
    }
    if (factors.size() > 2)
    {
        return false;
    }
    else return true;
}

int main()
{
  int percent = 0;
  long long max = 0;
  const long long NUM = 600851475143;
  long long num = NUM;
  for (long long i = 1; i < num; i++)
  {
      if(i % (NUM / 100) == 0)
      {
            percent++;
            cout << "Percent " << percent << "% completed.\n";
      }
      if (num%i == 0 && i > max)
      {
          if (isPrime(i))
          {
              max=i;
          }
      }
  }
  std::cout << max;
}

[Naughty Albatross]

Does that help? :)

[cire]

In the past, long == int

Is it true or am I wrong?

It may have been and still be true on certain platforms with certain settings. It has never been required, and assuming it has always been wrong.

Please don't supply solutions to people looking for help with Project Euler problems. If they wanted a solution, they could've googled one instead of asking for help with their existing code.

[Naughty Albatross]

Or :

#include <iostream>
#include <vector>
bool isPrime(long long num)
{
    std::vector<long long> factors;
    for (long long n=1;n<num;n++)
    {
        if (num%n==0)
        {
            factors.push_back(n);
        }
    }
    if (factors.size() > 2)
    {
        return false;
    }
    else return true;
}

int main()
{
  double percent = 0.00;
  long long max = 0;
  const long long NUM = 600851475143;
  long long num = NUM;

  std::cout.setf(std::ios::fixed);
  std::cout.precision(2);
  for (long long i = 1; i < num; i++)
  {
      if(i % (NUM / 10000) == 0)
      {
           percent+=0.01;
           std::cout << "Percent " << percent << "% completed.\n";
      }
      if (num%i == 0 && i > max)
      {
          if (isPrime(i))
          {
              max=i;
          }
      }
  }
  std::cout << max;
}

@cire
I didn't give him a solution. I am trying to make him feel a little bit better :)

[TheIdeasMan]

@closed account 5a8Ym39o6 (300)
> I didn't give him a solution

Don't give him badly implemented naive ideas either. You clearly don't understand the problem and there is no need for a percentage progress if it only takes 1 millisecond to run.

As for long or long long int, I wouldn't use either of those. Consider std::size_t, the number shouldn't be signed, and it is the largest unsigned type the system has. So this should work whether it is a 32 or 64 bit system.


@Runner
Some ideas:

You are using a naive method (trial division) of looking for prime numbers. Consider at least using Sieve of Eratosthenes (Google that on wiki) Look at Euler's method. Basically you only need to see if a number is a multiple of the primes before it, and there is a limit. The code for that is 2 lines.

Next realise with Project Euler that brute force solutions are not the answer: they either take too long, use too much memory, or overflow in one way or another. The idea is to to get one to think of a clever and efficient solution. This involves some research, wiki is your friend here. Even problem 1 is not directly obvious, it uses a formula rather than iterating. Also, previous solutions/ideas are helpful in solving later problems.

With this problem, consider if that 2 is not a factor of the number. So this means the largest factor must be smaller than number/2. As you find ever increasing small numbers which are not factors, the largest factor gets ever smaller. And you only need to check if primes are factors, not every number.

[Naughty Albatross]

@TheIdeasMan
> You clearly don't understand the problem and there is no need for a percentage progress if it only takes 1 millisecond to run.

It is you who clearly don't understand the problem at all.

ne555 wrote:

> The loop will run 600 BILLION times. If each iteration takes just one nanosecond, the program will run for 600 seconds, which is 10 minutes.

[TheIdeasMan]

>It is you who clearly don't understand the problem at all.

dhayden wrote:

The loop will run 600 BILLION times. If each iteration takes just one nanosecond, the program will run for 600 seconds, which is 10 minutes.

BS. I meant to solve the actual problem, not to provide some unnecessary output for the horribly inefficient brute force solution.

dhayden knows what he is talking about, and was commenting on the inefficiency of that particular method. He also said:

dhayden wrote:

I just wrote a solution that runs on a slow sparc system in less than 1 millisecond, so there's definitely room for improvement :).

I said:

TheIdeasMan wrote:

With this problem, consider if that 2 is not a factor of the number. So this means the largest factor must be smaller than number/2. As you find ever increasing small numbers which are not factors, the largest factor gets ever smaller. And you only need to check if primes are factors, not every number.

So I still maintain that it is you who doesn't know (or hasn't demonstrated that you do)

[Naughty Albatross]

@TheIdeasMan
Does BS really stand for :
http://txt.do/5e6w3

That is just what Google says.

[TheIdeasMan]

@ closed account 5a8Ym39o6 (300)

Yep, that is it. Sorry I am not apologising if it's not Politically Correct.

Does that help you? Good to hear :+)

[48T7M4Gy]

The situation with Project Euler is you can use whatever method you like and people do.

Brute force is just as acceptable and valid as the more sophisticated sieve solutions are where there is a tendency to misuse them as indicated by the sqrt function cropping up (fortunately not here) which indicates the point of the sieve has been missed.

However there are (more or less public) guidelines given by the 'PE rulers', albeit very brief, that you don't have to resort to huge integers beyond the usuals - long long etc - and a program is probably no good if it takes longer than a couple of minutes run time to solve the problem. (milliseconds is probably more appropriate but maybe somebody out there is plugging away on a Trash80.)

Above all anyone attempting the problems needs to read the question analytically and very very carefully. Every word/phrase has significance and PE3 is no exception.

If you use a sieve, focussing on 2 is a trivial worry, the fact is all numbers are sieved out the same way.

The fun and challenge of PE is getting the answer for yourself not getting someone to get it for you. If that was the case just Google it. :)

[TheIdeasMan]

@kemort

I hope you don't see this post as negative criticism, just genuine questions :+)

I mostly agree with what you have said, except that the fun and challenge is also about doing an efficient solution, and that is never a brute force solution. As I said earlier:

The idea is to to get one to think of a clever and efficient solution.

Project Euler wrote:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Note they mention mathematics as a basic idea, then mention computing and programming skills, so that in my mind is far from the brute force method of iterating every number.

kemort wrote:

..... where there is a tendency to misuse them as indicated by the sqrt function cropping up (fortunately not here) which indicates the point of the sieve has been missed.

Not sure what you meant about that - sqrt is a valid limit for prime numbers, at least for using Eratosthenes. Maybe you were talking other sieving methids?

kemort wrote:

If you use a sieve, focussing on 2 is a trivial worry, the fact is all numbers are sieved out the same way.

Just wondering :+), is that in relation to what I said? here:

TheIdeasMan wrote:

With this problem, consider if that 2 is not a factor of the number.

If so, that comment was about the larger problem itself (the factors), not in relation to finding primes. I mentioned it so the OP could get his thinking cap on, and set thinking mode to clever :+)

Anyway, I hope things are going well at your end :+)

Regards :+D

[48T7M4Gy]

TheIdeasMan

I hope you don't see this post as negative criticism, just genuine questions :+)

Not at all. It's all good.