How to factorize a number?

Question

I've been asked to factorize a number and show it in a specific way .

e.g: 100 = 2^2*5^2

This is the C++ code I've used so far with no dice , unfortunately:

#include <stdio.h>
#include <math.h> 

//IsPrime indicates whether a given number is or is not prime.
bool IsPrime(long long n)
{   
    int j = 3;
    if (n == 2)
    {
        return true;
    }
    else if (n % 2 == 0)
    {
        return false;
    }
    else
    {
        for (j = 3; j <= sqrt(n); j += 2)
        {
            if (n%j == 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main(void)
{
    long long n_orig,n, i=3 , primecount=0;
    scanf("%lld", &n_orig);
    n = n_orig;
    if (n == 1)
    {
        printf("1");
        return 0;
    }
    if (IsPrime(n))
    {
        printf("%lld", n);
        return 0;
    }
    if (n % 2 == 0)
    {
        while (n >= 2 && n % 2 == 0)
        {
            primecount++;
            n = n / 2;
        }
        if (primecount == 1)
        {
            printf("2*");
        }
        else
        {
            printf("2^%lld*", primecount);
        }
    }
    primecount = 0;
    n = n_orig;
    while (i <= n/2)
    {
        if (IsPrime(i))
        {
            while (n >= i && n % i == 0)
            {
                primecount++;
                n = n / i;
            }
        }
        n = n_orig;
        if (primecount == 0)
        {
            i++;
            continue;
        }
        if (primecount == 1)
        {
            printf("%lld*", i);
        }
        else
        {
            printf("%lld^%lld*", i, primecount);
        }
        primecount = 0;
        i+=2;
    }
    printf("\b");
    return 0;
}

Using this code I was able to generate a few test cases, though when I uploaded my answer to the website where the codes are presumably evaluated , out of 7 test cases (which I cannot know what they exactly are) , I pass 3 , fail 3 and exceed time limit (the one that hasn't even been declared in the question) in one case. I'd really appreciate some help , and please be noob-friendly!

Also , I don't really wanna know if my answer could be improved in some way , my top priority right now is understanding why MY own code doesn't work as intended.

P.S : Usage of iostream and arrays is not allowed.

Thanks in advance.

Have you stepped through your code with a debugger during execution? — Cory Kramer, Nov 02 '16 at 12:09
@CoryKramer I have actually but of course for relatively small numbers , since it can take quite while tracing it for big integers. And surprisingly enough , I haven't encountered an issue yet. — Minuano, Nov 02 '16 at 12:15
@gnasher729 Well 1 and 0 are definitely not primes. And also , I've used the sqrt function just once , in the IsPrime function I've myself have created. — Minuano, Nov 02 '16 at 12:15
Wrong, you are not using the sqrt function "just once". The `sqrt()` function gets called ***on every iteration of the loop***. You cannot rely on the C++ compiler optimizing it out. Every time the loop iterates, the loop condition is checked, and the loop expression gets evaluated. That's how C++ works. — Sam Varshavchik, Nov 02 '16 at 12:26
@SamVarshavchik Ahhh , I see ,so any reason why I'm getting "Wrong" instead of "Time Limit Exceeded" ? — Minuano, Nov 02 '16 at 12:32
@SauravSahu Much obliged! Though I'm still getting the same results — Minuano, Nov 02 '16 at 12:32
I think you can hardcode prime numbers up to let's say 1000 into an array and calculate bigger if necessary using it. That could speed up your code significantly — Slava, Nov 02 '16 at 13:06
the question talks about a C++ code, but the posted code is C. Please clarify — user3629249, Nov 05 '16 at 01:14
with `C` code, need to have the statement: `#include ` for the definition of `bool` etc. — user3629249, Nov 05 '16 at 01:16
for ease of readability and understanding, 1) separate code blocks (for, if, else, while, do...while, switch, case, default) via a blank line 2) follow the axiom: *only one statement per line and (at most) one variable declaration per statement.* — user3629249, Nov 05 '16 at 01:19

barak manos · Accepted Answer · 2016-11-03T07:35:30.473

1

Try this:

#include <stdio.h>
#include <math.h>

unsigned long long PrintMultiplicity(unsigned long long n,unsigned long long factor)
{
    unsigned int count = 0;

    while (n%factor == 0)
    {
        count++;
        n /= factor;
    }

    if (count > 0)
    {
        printf("%llu^%u",factor,count);
        if (n > 1)
            printf("*");
    }

    return n;
}

void PrintFactorization(unsigned long long n)
{
    unsigned long long factor;
    unsigned int add;

    printf("%llu = ",n);

    n = PrintMultiplicity(n,2);
    n = PrintMultiplicity(n,3);

    // Check only factors that are adjacent to multiples of 6
    for (factor = 5, add = 2; factor <= sqrt(n); factor += add, add = 6-add)
        n = PrintMultiplicity(n,factor);

    if (n > 1)
        printf("%llu^1",n);

    printf("\n");
}

int main()
{
    unsigned long long n;
    scanf("%llu",&n);
    PrintFactorization(n);
    return 0;
}

edited Nov 03 '16 at 07:35

answered Nov 02 '16 at 14:48

barak manos

29,648
10
62
114

Thanks! This one seems to be working. Two questions though , would you please explain how PrintFactorization works, and also I would like to know what seems to be wrong with my program , as mine and yours seem to be working alike, at least for a few test cases. – Minuano Nov 02 '16 at 16:56
@FuriousMathematician: I added a note above the line which you might find difficult to understand. – barak manos Nov 03 '16 at 07:08
I guess `add = 4-add` should actually be `add = 6-add`. – Henry Nov 03 '16 at 07:27
@Henry: Yes, good catch! Will speed things up a bit. Thanks for pointing that out!!! – barak manos Nov 03 '16 at 07:35
@barakmanos uhh , I'm kinda sure I'm starting to look like an idiot but I still can't quite figure out the algorithm you're using. What does "factors that are adjacent to 6" have to with anything? – Minuano Nov 03 '16 at 12:16
@FuriousMathematician: [5,7],[11,13],[17,19],[23,25],... All the numbers that are not divisible neither by 2 nor by 3. There is no point in checking all the rest, since that are obviously not prime. This reduces the number of tested factors by a magnitude of 3 (i.e., we are left with only one third of the original amount of factors to be tested). – barak manos Nov 03 '16 at 12:22
@FuriousMathematician: Please note that I've fixed `add = 4-add` to `add = 6-add`, thanks to Henry's comment (in case you're using this code anywhere)... – barak manos Nov 04 '16 at 16:08

score 0 · Answer 2 · edited May 23 '17 at 12:19

0

You need to perform some fine optimisations. Do not invoke isPrime() method for each value, instead consider a different approach so that irrelevant values can be ignored altogether at the very beginning.

Get the list of relevant primes numbers that comes under n, using Sieve of Eratosthenes concepts.
Start from the lowest prime value from the list, divide n to get intermediate values as

n / lowest_prime_that_perfectly_divide_n.

Continue doing this by checking with next higher prime value till n becomes 1. This way you would have count of each dividing factors.

edited May 23 '17 at 12:19

Community

1
1

answered Nov 02 '16 at 12:39

Saurav Sahu

13,038
6
64
79

Thanks ! I guess this'll have to do. – Minuano Nov 02 '16 at 13:31

Lutz Lehmann · Answer 3 · 2016-11-03T07:37:23.357

0

You do not need prime tests, and lists of primes or prime wheels are only needed for acceleration. A simple program listing all prime factors is

#include <stdio.h>
#include <math.h> 

int main(void)
{
    long long n_orig,n,k;
    scanf("%lld", &n_orig);
    n = n_orig;
    k=2;
    while(k*k<=n) {
        while(0==n%k) {
            n = n/k;
            printf("%lld ",k);
        }
        k++;
    }
    if(n>1) printf("%lld ",n);
    printf("\n");
    return 0;
}

This does not generate the required output format, but that can easily added to it.

edited Nov 03 '16 at 07:37

answered Nov 02 '16 at 13:56

Lutz Lehmann

25,219
2
22
51

This will increase `k` up to the largest prime factor of the initial `n`. One could stop much earlier (i.e. when k*k > n). – Henry Nov 03 '16 at 07:33
But then you have to treat the possibly remaining large prime factor separately. Done. – Lutz Lehmann Nov 03 '16 at 07:38
Yes, but it's worth it. The worst case runtime goes from O(n) to O(sqrt(n)). ;-) – Henry Nov 03 '16 at 07:45

How to factorize a number?

3 Answers3