Largest Prime Number with big numbers-CodePudding

I did a Project Euler question - here

I am at the end of my wits. I am getting wrong solution. I am perplexed as to "why" particularly this code is not working.

Relevant - this

This was my generated answer.

long long x; // The max prime factor
long long n; // The number to be factored
while (n % 2 == 0)
{
    n /= 2;
}
x = 2;
while (n % 3 == 0)
{
    n /= 3;
}
x = 3;
for (int i = 5; i <= sqrt(n); i  = 2)
{
    while (n % i == 0)
    {
        n /= i;
    }
    x = i;
}
std::cout << x;

n = 600851475143 answer = 6857>! I am getting x = 1471

CodePudding user response：

At least this for loop

for (int i = 5; i <= sqrt(n); i  = 2)
{
    while (n % i == 0)
    {
        n /= i;
    }
    x = i;
}

is wrong, The variable x gets the value of the last i that is less than or equal to sqrt( n ).

Consider for example n equal to 22. After dividing it by 2 you will get n equal to 11.

After this code snippet

while (n % 3 == 0)
{
    n /= 3;
}
x = 3;

x will be equal to 3 and the for loop will be skipped due to its condition that evaluates to false.

The code can look for example the following way

    long long int n = 600851475143;

    long long int prime_factor = 0;

    if (n % 2 == 0)
    {
        prime_factor = 2;

        while (n % 2 == 0 ) n /= 2;
    }

    for (long long int i = 3; i <= n / i; i  = 2)
    {
        if (n % i == 0)
        {
            prime_factor = i;
            while (n % i == 0) n /= i;
        }
    }

    if (n != 1) prime_factor = n;

    std::cout << "prime factor = " << prime_factor << '\n';

Also you should use the unsigned type unsigned long long int instead of the signed type long long int. Otherwise you will need to write code that will take into account the sign of the source number.

You could write a separate function as shown in the demonstration program below

#include <iostream>

unsigned long long max_prime_factor( unsigned long long int n )
{
    unsigned long long int prime_factor = 0;

    if (not ( n < 2 ))
    {
        if (n % 2 == 0)
        {
            prime_factor = 2;

            while (n % 2 == 0) n /= 2;
        }

        for (unsigned long long int i = 3; i <= n / i; i  = 2)
        {
            if (n % i == 0)
            {
                prime_factor = i;
                while (n % i == 0) n /= i;
            }
        }
    }

    return n < 2 ? prime_factor : n;
}

int main()
{
    for (unsigned int i = 0; i < 20; i  )
    {
        std::cout << i << " -> " << max_prime_factor( i ) << '\n';
    }
}

The program output is

0 -> 0
1 -> 0
2 -> 2
3 -> 3
4 -> 2
5 -> 5
6 -> 3
7 -> 7
8 -> 2
9 -> 3
10 -> 5
11 -> 11
12 -> 3
13 -> 13
14 -> 7
15 -> 5
16 -> 2
17 -> 17
18 -> 3
19 -> 19

CodePudding user response：

int main() {
  long long x = 0;            // The max prime factor
  long long n = 600851475143; // The number to be factored
  long long a = sqrt(n);
  while (n % 2 == 0) {
    n /= 2;
  }
  x = 2;
  while (n % 3 == 0) {
    n /= 3;
  }
  x = 3;
  for (int i = 5; i <= a; i  = 2) {
    while (n % i == 0) {
      n /= i;
      x = i;
    }
  }
  
  std::cout << x << std::endl;
}

Here it works, the sqrt(n) stoped the for loop too soon so i put it in a long long, and the x = i; was in the wrong place