Number of factors

[grandpascorpion]

Hello,

Maybe this is a naive question but I was wondering if there are any clever tests to determine the number of factors of a big integer. For instance, instead of a test revealing a number to be prime or composite, have the test reveal a specific number of factors, or at least/at most X factors.

I was thinking this could be somewhat useful when using ECM.

Even a test to reveal if a number had a square or other power of factor could be useful I think.

[xilman]

Originally Posted by grandpascorpion

Hello,

Maybe this is a naive question but I was wondering if there are any clever tests to determine the number of factors of a big integer. For instance, instead of a test revealing a number to be prime or composite, have the test reveal a specific number of factors, or at least/at most X factors.

I was thinking this could be somewhat useful when using ECM.

Even a test to reveal if a number had a square or other power of factor could be useful I think.

I hope it's not a naive question, but fear that it is.

As you note, such knowledge can greatly help the factorization problem.

An "at least / at most" function is easy to write, but useless. A number has at least one factor and at most floor(log_2(N)) factors. It's possible to produce a slightly tighter bounds without factoring (through a primality test, which can distinguish between at most 1 or at least 2) but nothing better is known.

Paul

[Orgasmic Troll]

According to Mathworld, testing a number to be squarefree is just as computationally intensive as factoring

[grandpascorpion]

Thanks, I suspected there wasn't anything known.

Originally Posted by grandpascorpion

Thanks, I suspected there wasn't anything known.

do you want to find the total number of factors for a nonprime number?

here`s a shortcut:-

take 12 for example, it canbe written as (2^2)*(3^1)

the powers of its prime factors are 2 and 1 , increment them once and then multiply , you`ll have the total number of factors as 3*2=6.

To verify it,just do a manual counting of the factors..

1,2,3,4,6,12<-----six in total

try this out for any number you can think of

so if a number can be factored as (a^b)*(c^d)*(e^f) then given a,c, and d are prime....the total number of factors will be (b+1)*(d+1)*(f+1).

[alpertron]

I think the original poster wants to know the number of prime factors of a big number without performing the actual factorization.