Find largest prime factor?

TheCreator (68)
I am able to do this for smaller numbers, but as soon as a get to larger numbers my program doesn't show output. I know my algorithim works, but how do I make it work with largers numbers. In this example Im trying to find the largest prime factor of 600851475143. I know I shouldn't use goto statements in good code, so please don't bug me about it.
Thanks for all help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <iostream>
using namespace std;
int main()
{
unsigned long long divisor=2; //divisor of 600851475143
unsigned long long pdiv=2; // divisor of divisor
unsigned long long lprime=1; // largest prime
ifloop:
if (600851475143%divisor==0)
{
    if (divisor%pdiv==0&& pdiv<divisor)
    {
        pdiv=2;
        divisor++;
        goto ifloop;
    }
    
    else
    {
        if (pdiv<divisor)
        {  
            pdiv++;
        goto ifloop;
    }
        else 
            lprime=divisor;
        divisor++;
        pdiv=2;
        goto ifloop;
    }
}
else
{divisor++;
pdiv=2;
if (divisor<600851475143)
{goto ifloop;}
else {}
}
cout<<lprime;
return 0;
}
Last edited on
buffbill (467)
A long will only hold an integer as large as about 2 billion and a long long is only guaranteed to hold no less than a long.......i think.
So try using a double which will hold about +1.7e308 to -1.7e308....I think.
Duthomhas (13282)
Nevertheless, on modern systems an unsigned long long will easily hold all your values.

TheCreator wrote:
I am able to do this for smaller numbers, but as soon as a get to larger numbers my program doesn't show output.
That is because you are doing so much work that when you get to larger numbers it takes a really long time to actually get to the part where your program prints output. The times for calculating with various numbers is given in the listing below.

And I am going to bug you about those gotos. Quit being lazy and just use a loop and continue statements.

Also, your formatting is confusing. You will help yourself to understand your algorithm much better if you use some consistent formatting. I have no other comment about your algorithm except that it needs serious improvement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include <iostream>
using namespace std;

//const unsigned long long value = 600851475143ULL;
//const unsigned long long value = 10000001ULL;    //   1 second
//const unsigned long long value = 100000001ULL;   //   5 seconds
//const unsigned long long value = 1000000001ULL;  //  47 seconds
  const unsigned long long value = 10000000001ULL; // 617 seconds (10 minutes 17 seconds)

int main()
{
  unsigned long long divisor=2; //divisor of value
  unsigned long long pdiv=2; // divisor of divisor
  unsigned long long lprime=1; // largest prime

  while (true)
  {
    if (value%divisor==0)
    {
      if (divisor%pdiv==0&& pdiv<divisor)
      {
        pdiv=2;
        divisor++;
        continue;
      }
      else
      {
        if (pdiv<divisor)
        {  
          pdiv++;
          continue;
        }
        else
          lprime=divisor;
        divisor++;
        pdiv=2;
        continue;
      }
    }
    else
    {
      divisor++;
      pdiv=2;
      if (divisor<value)
        continue;
    }
    break;
  }

  cout<<lprime;
  return 0;
}

Hope this helps.
Topic archived. No new replies allowed.