B*******1
发帖数: 2454 | 1 what is the time complexity of finding the number of devisors of a number? | b****y
发帖数: 93 | | S**I
发帖数: 15689 | 3 O(sqrt(n))
【在 B*******1 的大作中提到】
: what is the time complexity of finding the number of devisors of a number?
| a********1
发帖数: 750 | 4 sqrt(n)吧，只能一个一个的试
【在 B*******1 的大作中提到】
: what is the time complexity of finding the number of devisors of a number?
| r*******g
发帖数: 1335 | 5 I guess it is o(logn).
First, try to get N=a1^m1*a2^m2....which can be done iteratively.
Each step, try to find if it still contains primaries from a1 to ak, if yes,
increase m1 to mk, if not, try to find the next primary a_k+1. Since we
already maintained all the smaller primaries a1 to ak, we can just test the
next primary, and so on.
Then the result will be (m1+1)*(m2+1).....
【在 S**I 的大作中提到】
: O(sqrt(n))
| S**I
发帖数: 15689 | 6 You're assuming all the prime numbers are already known.
yes,
the
【在 r*******g 的大作中提到】
: I guess it is o(logn).
: First, try to get N=a1^m1*a2^m2....which can be done iteratively.
: Each step, try to find if it still contains primaries from a1 to ak, if yes,
: increase m1 to mk, if not, try to find the next primary a_k+1. Since we
: already maintained all the smaller primaries a1 to ak, we can just test the
: next primary, and so on.
: Then the result will be (m1+1)*(m2+1).....
| s**x
发帖数: 405 | 7 This must be way higher than O(logn).
Consider an extremely large number N. Primality test alone takes O((logn)^4)
. If N is composite and only has large factors, then you're screwed. | r*******g
发帖数: 1335 | 8 where did you get this O((logn)^4)?
testing whether primary might be an open problem. Even if it takes O((logn)^
4), that means after O((logn)^4) it is still primary, then, we already
ignore those small primaries which are not its divisor. We can still try to
find its primary divisor first. In this way, it is still quicker than
directly test sqrt(n) numbers.
In reality, primary numbers are known for some range. Find the primary
divisors should work fast. Otherwise, testing whether it is primary itself
is hard problem.
4)
【在 s**x 的大作中提到】
: This must be way higher than O(logn).
: Consider an extremely large number N. Primality test alone takes O((logn)^4)
: . If N is composite and only has large factors, then you're screwed.
| s**x
发帖数: 405 | 9 Please read this:
http://en.wikipedia.org/wiki/Primality_test
This is deterministic polynomial time.
Best known deterministic algorithm is AKS primality test in O((logn)^7.5).
Best practical probabilitic algorithm is Miller-Rabin in O((logn)^4) | S**I
发帖数: 15689 | 10 Primality test is not a hard problem, as the wikipedia link provided by shyx
shows. However, what's the complexity of finding all prime numbers smaller than sqrt(n)?
)^
to
【在 r*******g 的大作中提到】
: where did you get this O((logn)^4)?
: testing whether primary might be an open problem. Even if it takes O((logn)^
: 4), that means after O((logn)^4) it is still primary, then, we already
: ignore those small primaries which are not its divisor. We can still try to
: find its primary divisor first. In this way, it is still quicker than
: directly test sqrt(n) numbers.
: In reality, primary numbers are known for some range. Find the primary
: divisors should work fast. Otherwise, testing whether it is primary itself
: is hard problem.
:
| s**x
发帖数: 405 | 11 Well you can always use GNFS http://en.wikipedia.org/wiki/GNFS to completely factor N, then it is trivial to know the number of divisors.
Complexity is O((exp((64/9)^(1/3)+o(1))*((logn)^(1/3))*((loglogn)^(2/3))
It is not clear to me if there is an asymptotically faster method that does
not require factorization. | k****n
发帖数: 369 | 12 no way... there is no efficient algorithm for big integer factorization
yes,
the
【在 r*******g 的大作中提到】
: I guess it is o(logn).
: First, try to get N=a1^m1*a2^m2....which can be done iteratively.
: Each step, try to find if it still contains primaries from a1 to ak, if yes,
: increase m1 to mk, if not, try to find the next primary a_k+1. Since we
: already maintained all the smaller primaries a1 to ak, we can just test the
: next primary, and so on.
: Then the result will be (m1+1)*(m2+1).....
| p*****w
发帖数: 429 | 13 how did you get this?
for example, 16
sqrt(16) = 4
you only search 0 to 4?
I think it should be O(N)
【在 S**I 的大作中提到】
: O(sqrt(n))
| S**I
发帖数: 15689 | 14 think again :)
【在 p*****w 的大作中提到】
: how did you get this?
: for example, 16
: sqrt(16) = 4
: you only search 0 to 4?
: I think it should be O(N)
|
|
