0

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

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
Kartik Pandey
  • 39
  • 6
  • 2
    Unfortunately, as explained on project euler's web site, web sites like this are designed for people who are already experienced programmers, and who are looking to simply expand their skills. An experienced C++ developer will immediately recognize at least two fundamental problems with using `i <= sqrt(n)` as a loop condition, which makes the whole thing hopelessly broken. Unless someone's already an experienced C++ programmer, attempting to do one random coding puzzle after another will not accomplish anything, and nothing of value will be learned from that. – Sam Varshavchik Jan 19 '23 at 15:12
  • @drescherjm That will not be an issue. check [this](https://www.geeksforgeeks.org/find-largest-prime-factor-number/) – Kartik Pandey Jan 19 '23 at 15:12
  • 4
    You always assign to `x` regardless of if a number is a factor of `n` or not. – François Andrieux Jan 19 '23 at 15:13
  • 1
    That code still won't work if there is one big prime factor. You should only return `x` if `n` is not 1. (And please try to use more meaningful variable names.) – rici Jan 19 '23 at 15:38
  • `i*i <= x` i much faster than `i <= sqrt(x)` or `long long a = sqrt(i);` and than `i <= a` – Darkolin Jan 19 '23 at 15:47

2 Answers2

0

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
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • `i <= n / i` this was brilliant, we avoided extra library and the computation would be simpler as well. Moreover, I found merging ifs and whiles would have been fine. But we have avoided the iterative assignment of prime factor. Thats cool as well. Furthermore, I found we could have used [this](https://www.youtube.com/watch?v=pOKuLSKnAW4) Thanks Vlad. A question at the end - This was the trial division method of prime factorization. What would be the fastest method to do this? (without taking an array of primes thats cheating!) – Kartik Pandey Jan 20 '23 at 10:17
  • @KartikPandey I am sorry. I have not though about that yet.:) – Vlad from Moscow Jan 20 '23 at 10:19
-3
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

Luken
  • 3
  • 2