The prime factors

Question

The question is to write a number n as a product of its prime factors in C++

For example 14 = 2*7

24 = 2*2*2*3

5 = 5.

My code is :

#include <iostream>
#include <cmath>
using namespace std;
bool prime(int n)
{
    for (int i=2;i<=sqrt(n);i++)
        {
            if (n%i==0) return false;
        }
    if (prime) return true;
}

int main ()
{
    int n;
    int k=0,a[10000]={0};
    cin>>n;
    while (n!=1)
        {
            for (int i=2;;)
                {
                    if (n%i==0 && prime(i)) {n/=i; a[k]=i;k++; }
                    else i++;
                    if (n==1) break;
                }
        }
    cout<<a[0];
    int s=1;
    while (a[s]!=0)
        {
            for (s=1;;s++)
                {
                    if (a[s]==0) break;
                    cout<<"*"<<a[s];
                }
        }
    return 0;
}

But the problem is time limit and the compiler_stderr.txt shows me this message:

solver.cpp: In function `bool prime(int)':
solver.cpp:11: warning: the address of `bool prime(int)', will always evaluate as `true'

And when I enter 2147483647 it shows me this number again but after 5 or 6 seconds

That's an obvious message, for this line: `if (prime) return true;`. When did you intended it to return 'true'? — Jongware, Apr 19 '14 at 19:46

score 2 · Answer 1 · answered Apr 19 '14 at 19:47

The warning is regarding this line:

if (prime) return true;

This doesn't call the function, it just tests the value of the function pointer. Since it's not a null pointer, it's always true.

If you reach that point in the function, none of the tests for divisors succeeded, so you should just return true without testing anything.

The reason your program takes so long to return an answer is because you're using an inefficient method to test for primes. You should only be testing other primes, using the Sieve of Eratosthenes. Also, you should call sqrt(n) just once, before the loop, and save its value in a variable; calculating the square root is expensive, so you don't want to do it every time.

score 0 · Answer 2 · answered Apr 19 '14 at 19:47

0

I don't think you should be checking if prime is defined before your return true.

Try the following instead

bool prime(int n)
{
    for (int i=2;i<=sqrt(n);i++)
    {
        if (n%i==0) return false;
    }
    return true;
}

answered Apr 19 '14 at 19:47

Shakeel

1,039
7
20

score 0 · Answer 3 · answered Apr 19 '14 at 19:48

Read the warning message. Put into your mind that the compiler has a reason and doesn't give that warning just for fun. Once you do that your mistake is easy to find:

if (prime)

prime is the name of a function. In many situations, the name of a function is automatically converted to the address of the function. In an if statement, the controlling expression is checked for being zero or not zero. The address of the function prime is never a null pointer, so the "if" expression will always evaluate to true.

score 0 · Answer 4 · answered Apr 19 '14 at 20:40

There's no need for a prime function with the current code. Just repeatedly checking for (n%i) == 0 will eliminate any powers of prime numbers, since it will keep adding i into k[] until there are no more factors of i. Assuming that 4 is a factor of n, then when i reaches 4, it won't be a factor because it was already divided out with n /= i when i was 2, (k[0]=2, k[1]=2). k[] will end up with the prime factors of n without the need for a prime function.

score 0 · Answer 5 · edited May 23 '17 at 10:26

Since the address of prime is never zero, it will always return true. So the program would work perfectly. Although maybe you want to write it in a more readable way: return true; and remove the condition checking.
2147483647 is a very large number and your program runs in O(n^1.5) time. So you may assume it is running in the order of 2147483647^1.5 times. Hence the time delay for the output. You may try to reduce the complexity by using a different method like this.

The prime factors

5 Answers5