CODEWITHSUNDEEP
c++factors
rahulk
rahulk

Reputation: 175

how to find all factors of a given number N with time complexity less then N?

i am trying this but on input>10000 this loop id taking much more time.

is there is any way to optimize this which has time complexity less then N or (logn)?

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
    int n = 10001;

    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            cout << i;
        }
    }
    return 0;
}

Upvotes: 0

Views: 5623

Answers (4)

ST3
ST3

Reputation: 8946

In case you need to perform this many times, there is a good solution. I'll give just an example, implementation will be your business.

Lets say you need to factorize two numbers, e.g. 580 and 72.

At first you factorize it into primes

580 = 2 x 2 x 5 x 29
72 = 2 x 2 x 2 x 3 x 3

Speed of factorization into primes could be highly increased using caching. You should have std::set<int> which contains all know prime numbers, so after factorizing 580 it contains 2, 5, 29. That means to factorize 72 you will only need to determine that 3 is prime.

After you have all prime factors you need to multiply them in all combinations to get non-prime factors.

As I mentioned this solution is really good only in case you need to factorize many numbers, but if you need to factorize only once it is just not bad Sieving would be better.

Upvotes: 0

TonyK
TonyK

Reputation: 17114

First step is to find all the prime factors, with their multiplicity. Then you can generate the factors easily.

Finding the prime factors is quite fast on average for numbers up to about 100000000, if you do it sensibly. If you find a factor, you can divide it out of n, which reduces the time enormously in the general case. Also you only need to check odd factors up to sqrt(n), apart from 2:

// I assume n is non-zero
while (!(n & 1)) {
    cout << "2" << endl;
    n /= 2;
}
for (unsigned int factor = 3; factor * factor <= n; factor += 2) {
    while (n % factor == 0) {
        cout << factor << endl;
        n /= factor;
    }
if (n != 1)
    cout << n << endl;
}

Upvotes: 1

dmh2000
dmh2000

Reputation: 683

you can iterate up to just the square root of n rather than n, since anything bigger than the square root can't be a factor of n. edit : read ComicSansMs answer was better than my edit

Upvotes: 1

ComicSansMS
ComicSansMS

Reputation: 54589

In addition to dmh2000's answer: You can exploit redundancies in the checking. For example, if a number is not divisible by n it is also not divisible by any multiple of n. For example a number that is not divisible by 2 also cannot be divided by 4, 6, or 8.

This technique is known as sieving.

Upvotes: 2

Related Questions