0

I want to open by saying that I am not very good at programming yet and there is probably a better way of doing what I want to. If looking at things that are so blatantly bad annoy you, then move on.

I’ve been giving a shot at the third question for Project Euler which is “Find the largest prime factor of 600851475143.” First I made something that calculates the factors of a number. (Excuse the names, I couldn’t think of anything.)

#include <iostream>

using namespace std;

void Factor (double dFactorer)
{
    long dUpperlimit;
    dUpperlimit = (int)dFactorer/2;
    float fnumTouse;
    fnumTouse = 1;
    int nCounter;
    nCounter = 0;
    while (fnumTouse <= dUpperlimit)
    {
        if ((long)dFactorer % (long)fnumTouse == 0)
        {
            cout << fnumTouse << endl;
            fnumTouse++;
            nCounter++;
        }
        else
        {
            fnumTouse++;
        }
    }
    cout << dFactorer << endl;
    cout << "There are " << nCounter + 1 << " factors in this number";
}

int main()
{
    double dNumtofac;
    cout << "Enter a number to factor: ";
    cin >> dNumtofac;
    cout << endl;
    Factor (dNumtofac);
    return 0;
}

Alright, so, I know it’s a really shoddy job, what with all the casting I had to do to make certain things work. It works with smaller numbers but anything around the 100 millions makes it only output a certain number of factors before completely stopping. I tried the problem number, and it’s output was the number itself, saying that there is only one factor in this 600851475143. I’d like to know why it says this, is it something to do with the limits of the variables that I used? Something else? I don’t have enough knowledge to figure this out.

Pat Nak
  • 31
  • 1
  • 6
  • Not sure why this was downvoted but I think this question may be better suited to http://codereview.stackexchange.com/ perhaps – EdChum Oct 24 '13 at 09:04
  • @EdChum I don't think so. It has a specific problem: it does not produce the correct answer. – BoBTFish Oct 24 '13 at 09:06
  • The max value for `int` variable is 2147483647 on 32-bit platform, so don't expect your code to process larger numbers – Andriy Oct 24 '13 at 09:06
  • @PatNak You are using way too many types of numbers (I see all of `int`, `float`, `long`, `double`). You should only need one type, and it should be an integer type. Also, the input number will not fit into a 32 bit type. I suspect this is deliberate. (`int` is 32 bit on most platforms. Play with `sizeof`, which returns the size in bytes. Try `long`.) – BoBTFish Oct 24 '13 at 09:09
  • Also, cut bad habits early by reading [this](http://stackoverflow.com/q/1452721/1171191) and [this](http://kuhllib.com/2012/01/14/stop-excessive-use-of-stdendl/). – BoBTFish Oct 24 '13 at 09:12
  • @BoBTFish Alright I'll try to bring everything to a `long` and check what the sizes are. Thanks! – Pat Nak Oct 24 '13 at 09:15
  • @BoBTFish I just checked the sizes for my `int` and `long`, they are both 4 bytes so will changing the `int` to `long` do anything? I looked at a graph and saw that I would need at least an 8 byte variable to fit the problem number (which for me is a `double`). The only thing with this is that I'm pretty sure that modulo cannot be used with a `double`. – Pat Nak Oct 24 '13 at 09:24
  • You also need to think carefully about what your function is trying to do. Do you want it to print *all* factors? or all *prime* factors. Your current code does neither; if you stop half way you can't get all factors, and you may get non-prime factors. I suggest starting from `2` counting up. When you find a factor, **divide it out** and carry on. Make sure you get any factor that can appear multiple times (`20=2*2*5`). This will give you the primes. You can set your upper limit to the square root of the input, and if you hit it before your input has been reduced to `1`, the input is prime. – BoBTFish Oct 24 '13 at 09:28
  • @PatNak Ah ok. You need a 64 bit integer type. The best possibility is to `#include ` and use `std::int64_t`. Are you enabling `C++11`? If so it should work. If not, try `` and just `int64_t`. – BoBTFish Oct 24 '13 at 09:30
  • @BoBTFish Thanks for all the help ( the comments and those two articles ) I'll revise and take what you said into account. – Pat Nak Oct 24 '13 at 09:32
  • @PatNak No problem. I'm trying to help you figure it out, rather than just give you a chunk of working code (which I would have to rewrite from scratch, as my PE solutions are at home). – BoBTFish Oct 24 '13 at 09:35
  • @BoBTFish Yeah, that method helps more than just giving me the correct code, I get to learn more and I appreciate it. I'll give this another shot in the morning when I get some sleep and see how it goes. – Pat Nak Oct 24 '13 at 09:39
  • @BoBTFish Thanks again for all the help you gave, I got it working correctly after taking what you said into account. I haven't been doing this for a very long time and I really do appreciate help like this. – Pat Nak Oct 25 '13 at 06:41
  • Actually I just realised my recommendation was rubbish. If you reduce the target number and increment up to the original square root, you may miss one (the largest) prime factor. – BoBTFish Oct 25 '13 at 07:30

1 Answers1

0
#include <iostream>

using namespace std;

int main()
{
long long n=0;
//to do: verify that the number is positive and below the limit of long long
cout <<"The number to factor : ";
cin  >>n;
long long aux = n%2==0 ? 2 : 1;
for (long long i=3;i<=n/2;i+=2)
    if(n%i==0)
         aux = aux>n/i ? aux : n/i;
cout<<"Greatest factor = "<<aux;
return 0;
}

Of course, you can greatly improve this by making the for go from high to low and stop at the first occurrence of a factor. Don't forget to verify if n/2 is odd or even. (Didn't test the code).

StefanS
  • 1,089
  • 1
  • 11
  • 38