Problem 003

[ClockworkMan986]

Wow, didn't think about that.

I'm running it now with long long x. It's hanging up on 716151937 again, so I'll need to optimize it a bit, but it's not returning negatives, so that's a huge step up. Thanks for that.

Edit: As I wrote that message another factor came up, so it's just super slow, which I 'll worry about once I get this working.

Awesome! Step 1 is complete.

I am trying to return a value of these factors as a variable of prime, now. prime will be the modulus of the factor (x) and a dividend (a). a will keep rising through numbers until it hits the limit, but that is irrelevent at the moment because when I have prime display itself, it returns as one no matter what. Any suggestions as to how I am doing this wrong?

Here is the code reflecting this next step. I checked my variables, so it's all capable of storing, but for some reason the != 0 in the if statement doesn't work correctly:

Code: Select all

/*
Project Euler Problem 3 - I can produce all factors of a number; but it
stops working when I go for the prime number

Also, large numbers murders it.
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

int main(int nNumberofArgs, char* pszArgs[])
{
    long long x = 1LL;
    long long a = 2;
    long long limit = 13195LL;
    long long factor = 0LL;
    int prime = 0;

    for (;x <= limit; x++)
    {
      factor = limit % x;
      if (factor == 0)
      {
        for (; a <= limit; a++)
        {
          prime = x % a;
          if (prime != 0)
          {
            cout << x
                 << " is a prime factor of "
                 << limit
                 << "."
                 << endl;          
          }    
        }
        
      }
    }
       
    //wait until user is ready before terminating program
    //to allow the user to see the program results
    system ("pause");
    return 0;
}    

[jaap]

1) Think about your variable a. It starts off with value 2. After the first divisor is found, a is increased by the loop up to limit. So what happens when the next divisor x is found?

2) What is the intention of this for loop of a? What happens when a==x ?

3) It seems you are trying to find all divisors, and then checking to see if the divisor is prime. There are much faster ways to factorise a number. Hint: can the smallest divisor be composite?

p.s. 'factor' is the wrong name for that variable. It should be called 'remainder' or something like that.

[ClockworkMan986]

I'll have to really ponder these questions a bit. I was, unfortunately, a slacker in my math classes since my degree didn't require it, so I never developed that solid mathematics foundation nor the thought process required to build one. Now that my job requires me to eventually do deep and complex programming, I came to this site to improve both skills simultaneously.

Let's see if I am capable of figuring this out. Thanks for the heading me in the correct direction.

1) Think about your variable a. It starts off with value 2. After the first divisor is found, a is increased by the loop up to limit. So what happens when the next divisor x is found?

2) What is the intention of this for loop of a? What happens when a==x ?

The program SHOULD loop to the next x, but instead it returns the value of 1 in to the variable prime while a starts at 2 and goes to my limit (regardless of the limit). Prime is set for the remainder of x / a, but for some reasons it's returning the same remainder regardless... hmm...

Moving to the next question (which ties into the end of the former question) when the next divisor is found it SHOULD cycle that previous loop, but it doesn't. If I change x to 3LL, I return prime as 5 and x as 5. AH, so instead of having a hit the limit, I should have the loop of a stop when it is equal to x since anything above x is irrelevant because it'll be less than 1, which is useless for this exercise. With x = 1LL, I go back to a loop of returning prime as 1 and x as 1, so I will have to check out the logic of this section again. Thanks for that tip!

3) It seems you are trying to find all divisors, and then checking to see if the divisor is prime. There are much faster ways to factorise a number. Hint: can the smallest divisor be composite?

p.s. 'factor' is the wrong name for that variable. It should be called 'remainder' or something like that.

I'm not sure what you mean for the hint, but if I follow correctly, the smallest divisor cannot be composite. The problem is I'm not sure what to do with that information yet.

Thanks for the tip on the naming convention. I need to make it a habit to make my variable names as clear as possible.

I think I covered your response. Thanks again for the direction hints. I am feeling good about this example, but I feel I am missing something small but critical =\

Edit: My "prime checking" loop is my ultimate problem, but I cannot figure out what I am doing wrong.

I changed my limit to 100 which yielded the factors 1, 2, 4, 5, 10, 25, 50, and 100. This part of the program worked by reducing all possible factors to just ones that evenly go into 100. My next problem is when running my prime check, it fails across the board.

For sake of clarity:

Code: Select all

for (; a != x; a++)
        {
          
          /*prime = x % a;
          if (prime != 0)
          {
            cout << x
                 << " is a prime factor of "
                 << limit
                 << "."
                 << endl;          
          } 
        }

The loop fails entirely because I took out all other factors of it (solving for a itself) and it just created a loop of the same output for infinity. I believe that reduces the issue to the opening declaration, but I am not sure how else to declare/set this loop to run...

[jaap]

... while a starts at 2 ...

More explicitly: Where in the code is a ever reset to 2 ?

[ClockworkMan986]

Wow, I completely forgot about resetting a. Would adding a = 2 in my for statement correct this issue? When I ran that change, and added in some breaks, I was able to get two prime factors to report: 5 and 25. 25 being divisible by 5, I know I am close to solving this example. Here is my changed for loop. I promise this is my last request for help:

for (a = 2; a != x; a++)
{

prime = x % a;
if (prime != 0)
{
cout << x
<< " is a prime factor of "
<< limit
<< "."
<< endl;
break;
}
else
{
break;
}

I think this program has taught me the most because now I will be more conscious of resetting my variables. This could explain why a few other programs I have were not working!

Edit: I tried the example number on the problem (13,195) and it still isn't reducing prime numbers, but showing all factors. I may have to scrape this attempt for now until I can get a better handle on how to do problems like this =\

[ClockworkMan986]

Any tips on how to approach this? I can reduce my list of numbers to factors, but I cannot reduce to them to prime factors. I know I am missing something simple in the coding because I tend to overthink simple concepts. If someone could point me in the correct direction, I know I can solve this.

[jaap]

Your code two posts up accepts x as a factor whenever there is ANY smaller number that doesn't divide it. You want to accept x only if it is prime, i.e. when NONE of the number smaller than x divide it.

[rayfil]

When you find a prime factor, continue working only with the quotient.

For example, with 195, the first prime factor would be 3. The quotient would then be 195/3=65.
The next prime factor you would find is 5, resulting in a quotient of 65/5=13. etc.
Don't forget than some integers may have the same prime factor more than once, ex.: 8=2*2*2

[Unz]

@rayfil

When you find a prime factor, continue working only with the quotient.

You have managed to sum it all up in just one sentence.

[ClockworkMan986]

This makes a lot more sense. I'm going to solve this problem now. Thanks for the advice.

[rineez]

Anybody done this in java?
I'm working with java and i am confused which data type to use to hold this number 600851475143.
My compiler is showing error "integer number too large: 600851475143" !
But I thought this number is within the range of long.

[jaap]

Anybody done this in java?
I'm working with java and i am confused which data type to use to hold this number 600851475143.
My compiler is showing error "integer number too large: 600851475143" !
But I thought this number is within the range of long.

It does fit in a long, but it tries to interpret the literal number 600851475143 as an integer during compilation, and this fails. You must put an L at the end of the number to indicate that it is to be interpreted as a long integer.
long m = 600851475143L;

[rineez]

thanks alot jaap.

[rineez]

Solved in: 140 milliseconds
Is that good?
By the way I was using benchmarking code from http://java.sun.com/docs/books/performa ... nt.fm.html for measurement.
This was showing '0 milliseconds' for Problem 1 .! is that a correct measurement?

[jaap]

This was showing '0 milliseconds' for Problem 1 .! is that a correct measurement?

Although currentTimeMillis gives a time in milliseconds, that doesn't mean it is accurate to the millisecond. I think it gets updated roughly every 20 or 30 ms, so it cannot measure more accurate than that. In particular, if you have a program that runs in less than 20ms, then it may seem to take 0 ms because currentTimeMillis hasn't been updated during that interval.

To get a better measurement, run the code a hundred times during one measurement, and divide by 100.

[rineez]

To get a better measurement, run the code a hundred times during one measurement, and divide by 100.

aah. thanks again..

[Lord_Farin]

To get a better measurement, run the code a hundred times during one measurement, and divide by 100.

What about System.nanoTime()? I mostly use it for solving problems, and it appears that it is quite accurate. Although of course 100 executions will filter out most processor occupation spikes.

[jaap]

What about System.nanoTime()? I mostly use it for solving problems, and it appears that it is quite accurate.

I didn't know about that one. Still, the documentation says there are still no guarantees about the accuracy/granularity, only that it is the most accurate timer available.

[Ocifer]

I was able to solve the problem, and my algorithm seemed to do it almost instantaneously. However, I've noticed some curious behaviour. Numbers far less than the given number can take longer, some under a minute, some a bit more. Was the number from question #3 chosen because it had relatively low prime factors? (I mean low from a computational viewpoint)

I've crunched some nastier numbers which took anywhere from under a minute to 3 minutes; these ended up having prime factors with 8 to 10 digits. Is this just the nature of the beast? Are there are any other methods? I've looked at the Sieve of Eratosthenes, and similar methods, but I don't see the advantage; one would still have to store the primes up the number being factored... My algorithm used the approach of narrowing the scope of factorization by using the quotient without having to store many very large numbers. The downside is that checking for primeness of a factor is intensive. Can anyone point me to some other approaches?

[harryh]

I suggest you try the Sieve of Eratosthenes and some of its variants / improvements. You'll suprised !