Why is this code not printing the prime factors of num?

Question

I wrote this code for obtaining the prime factors of a number taken as an input from the user.

#include<bits/stdc++.h>
using namespace std;

void prime_Factors(int);
bool isPrime(int);

int main()
{
    int num;
    cout << "Enter the number to find it's prime factors: ";
    cin >> num;
    prime_Factors(num);
}

void prime_Factors(int n1)
{
    for(int i = 2; i<n1; i++)
    {
        if(isPrime(i))
        {
            int x = i;
            while(n1%x==0)
            {
                cout << i << " ";
                x *= i; 
            } 
        }
    }
}

bool isPrime(int n0)
{
    if(n0==1)
        return false;
    for(int i = 0; i*i <= n0; i++)
    {
         if(n0%i==0)
            return false;
    }
    return true;
}

The prime_Factors() function call in main() function is not printing the prime factors. Pls help!!

`#include` says to me "I don't know how to program in C++, and I am learning from a resource that is teaching me how to program in C++ wrong". — Eljay, Jul 14 '22 at 13:31
Just as a side note: [Why should I not #include ?](https://stackoverflow.com/q/31816095/12149471) — Andreas Wenzel, Jul 14 '22 at 13:41
Your `prime_Factors()` function only attempts to print prime factors of values for which `isPrime()` returns true. So it won't attempt to print prime factors of composite (non-prime) values. — Peter, Jul 14 '22 at 14:00
Your loop should start at 3, then increment by 2. The number 2 is the only even prime. Since it's an exception, handle it before the loop. — Thomas Matthews, Jul 14 '22 at 15:18
As MikeCAT says your `isPrime` is UB. Besides that you should replace `while(n1%x==0) ` with `while((n1 > 1) && (n1 % i == 0))` and `x *= i;` with `n1 /= i;`. That way `prime_Factors(100)` only has to test 2, 3, 4, 5. Your loop also only needs to go up to `i * i <= n1` if you print `n1` at the end if it isn't `1`. — Goswin von Brederlow, Jul 14 '22 at 22:48
Other optimizations: handle `2` as special case and only test odd numbers in the loops. Generating a Sieve of Eratosthenes up to n can also be faster. Actually you can combine that with printing prime factors. When you mark bits in the sieve if you hit `n` you have a prime factor. Print it and divide `n / factor` as often as possible. `prime_Factors(100)` would only need a sieve up to 25 and only test 3 and 5. — Goswin von Brederlow, Jul 14 '22 at 22:53
Note: if you do the optimization with `n /= i`; you can remove the `isPrime` test. https://godbolt.org/z/xTWfPaq7n — Goswin von Brederlow, Jul 14 '22 at 23:16

score 7 · Accepted Answer · answered Jul 14 '22 at 13:26

The ranges of the loops are wrong.

Firstly, the loop for(int i = 2; i<n1; i++) will fail to find prime factors of prime numbers (the numbers theirself). It should be for(int i = 2; i<=n1; i++).

Secondly, the loop for(int i = 0; i*i <= n0; i++) will result in division-by-zero. It should be for(int i = 2; i*i <= n0; i++).

Goswin von Brederlow · Answer 2 · 2022-07-14T23:14:52.697

Thinking about using the Sieve of Eratosthenes made me try it out:

#include <iostream>
#include <cstdint>
#include <vector>

void prime_factors(uint32_t n) {
    while(n % 2 == 0) {
        std::cout << "2 ";
        n /= 2;
    }
    std::vector<bool> sieve(n / 2, true);
    for (uint32_t i = 3; i * i <= n; i += 2) {
        if (sieve.at(i / 2 - 1)) {
            uint32_t j = i * i;
            for (; j < n; j += 2 * i) {
                sieve.at(j / 2 - 1) = false;
            }
            if (j == n) {
                do {
                    std::cout << i << " ";
                    n /= i;
                } while (!sieve.at(n / 2 - 1));
            }
        }
    }
    if (n > 1) std::cout << n;
    std::cout << "\n";
}

int main() {
    prime_factors(123456789);
}

https://godbolt.org/z/8doWbYrs6

Why is this code not printing the prime factors of num?

2 Answers2