C++

Forum

 
How solve problem, am too dumb...

creekist (109)
I posted the following on stackoverflow:

I'm working on Interview Street's "Unfriendly Numbers" puzzle.

It goes like this:

Given an integer, and another list of integers, find the factors that are only unique to the given integer, and are not shared with the other list of integers.

So if set 1 (set Y) is (and n is the given number):

∃Y{z|n % z = 0}

Basically: There is a Y for every z, where z is a number where n % z is 0.

We want the set difference for Y minus the set that contains all the factors of the other list of numbers.

So how would you approach this?

Find the factors of integer n? All the factors of the other numbers and just weed out the non-unique factors?

Or would you only find the factors of n and just use them to divide the other numbers and weed out the non-unique ones?

Or is there a way to do it without factoring the number?

Thus far I've used Trial Division, Pollard's Rho, Brent's variation of Pollard's Rho and Fermat's method for factorization. I've also made use of the Lucas-Lehmer primality test and Euclids GCD.

But thus far, nothing, just a combination of wrong answers or exceeding the time limit.

Sigh...

Any thoughts, one guy on the internetzzzz solved it using a wheel prime sieve, not sure what that is.

Thanks anyways.


I'm just looking for some general thoughts.
Duthomhas (13155)
You only need to completely factorize the given integer. This gives you a list of factors (which should be relatively small).

Next, for each factor in your list of factors, check that it is not a factor of any integer in your list of integers. (If it is, remove it from the list of factors.)

Hope this helps.
creekist (109)
Right,

So how does one rapidly factor a given number, because apparently the ways I've been doing it are too slow. Or they just give wrong answers.

Ugh.
JLBorges (13770)
> So how does one rapidly factor a given number

If the number is reasonably small (for instance, one that can be held in a long long), a brute force approach would be more than fast enough:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <vector>
#include <cmath>
#include <algorithm>

std::vector<long long> generate_all_factors( long long n )
{
    const long long ub_root = (long long)( std::sqrt( double(n) ) + 2 ) ;

    std::vector<long long> factors ;
    for( long long i = 1 ; i < ub_root ; ++i ) if( n%i == 0 )
    {
        factors.push_back(i) ;
        factors.push_back(n/i) ;
    }

    std::sort( factors.begin(), factors.end() ) ;
    factors.erase( std::unique( factors.begin(), factors.end() ), factors.end() ) ;
    return factors ;
}
NYK (9)
I don't understand what you want.
creekist (109)
I don't understand what you want.


Evidently the quote:

I'm just looking for some general thoughts.


Wasn't enough for you.

I guess I'll say it again:

I'm just looking for some general thoughts.
creekist (109)
@JLBorges

I used the brute force approach, it passed the first 3 test cases, but was too slow for the last 3.
NYK (9)
ok then i would definitly use a while or for loop.

and I found this website.

http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization-calculator.php

also what is the time limit exactly?
JLBorges (13770)
> but was too slow for the last 3.

How big are these numbers? And how slow is too slow?

I get:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <ctime>

std::vector<long long> generate_all_factors( long long n )
{
    const long long ub_root = (long long)( std::sqrt( double(n) ) + 2 ) ;

    std::vector<long long> factors ;
    for( long long i = 1 ; i < ub_root ; ++i ) if( n%i == 0 )
    {
        factors.push_back(i) ;
        factors.push_back(n/i) ;
    }

    std::sort( factors.begin(), factors.end() ) ;
    factors.erase( std::unique( factors.begin(), factors.end() ), factors.end() ) ;
    return factors ;
}

int main()
{
    const long long numbers[] = { 4199040000LL, 864568320061LL, 478585848547436LL,
                                    5454091843200000LL, 54540918432000000LL  };
    for( long long n : numbers )
    {
        std::clock_t start = std::clock() ;
        std::vector<long long> f = generate_all_factors(n) ;
        std::clock_t end = std::clock() ;
        std::cout << n << ": " << f.size() << " factors in "
                  << (end-start)/double(CLOCKS_PER_SEC) << " seconds.\n" ;
    }
}

Output:
4199040000: 495 factors in 0 seconds.
864568320061: 4 factors in 0.051 seconds.
478585848547436: 24 factors in 0.902 seconds.
5454091843200000: 14256 factors in 3.207 seconds.
54540918432000000: 18144 factors in 10.441 seconds.

creekist (109)
ok then i would definitly use a while or for loop.

and I found this website.

http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization-calculator.php

also what is the time limit exactly?


Thanks dude, the time limit is 3 seconds for C++ and 16 seconds for Python, I'm using Python.
creekist (109)
How big are these numbers? And how slow is too slow?


They won't let you see the test cases, 16 seconds is the time limit for Python and 3 seconds is the time limit for C++.
Duthomhas (13155)
That is a lot of time.

I think it is likely that you are doing something the hard way.

There is a simple trick to factoring. You need two lines: one line starts with the number you are factoring, the other line starts with the number 1. (Both are factors of the number you are factoring.) For convenience in this example, the top line will start with the number to factor and the bottom line will start with one.

Start counting up from one. If the number is a factor, write it down on the bottom line. Calculate (number_to_factor/factor_just_found), and if it is not the same as factor_just_found, write it down on the top line above the number you just wrote down. (Because this new number is also a factor.)

Once you count up to the last number on the top line, you are done.

For example, factors of 24:
  24  12   8   6
   1   2   3   4    (5 is not a factor, and 6 is the last number on the top line)

Factors of 36:
  36  18  12   9  (6 is already written below)
   1   2   3   4   6

For any native integer in your computer, this algorithm is more than fast enough. Keep in mind that you don't need two "lines" here, you only need to remember the last (number_to_factor/factor_just_found).

Hope this helps.
creekist (109)
Thanks!

I tried it that way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
import sys

nandk = sys.stdin.readline();

nandk = nandk.rstrip();

nandk = nandk.partition(" ");

unfriendly = sys.stdin.readline();

unfriendly = unfriendly.rstrip();

unfriendly = unfriendly.split(" ");

nomean = int(nandk[0]);

friendly = int(nandk[2]);

divisors = [];

primes = [];

counter = 1;

while counter < int(friendly**0.5) + 1:

    if friendly % counter == 0:

        divisors.append(counter);

        if (friendly / counter) != counter:

            divisors.append(friendly / counter);

    counter += 1;

counter = 0;

while counter < nomean:

    meanone = int(unfriendly[counter]);

    othercounter = 0;

    while othercounter < len(divisors):

        divisor = divisors[othercounter];

        if meanone % divisor == 0:

            divisors.pop(othercounter);

            othercounter -= 1;

        othercounter += 1;

    counter += 1;   

print len(divisors);


Apparently it was still too slow for the last 3 test cases.

The time exceeding 16 seconds.
Topic archived. No new replies allowed.