算法找到给定数量..最短方法的因素？ [英] Algorithm to find the factors of a given Number.. Shortest Method?
问题描述
可能是什么简单省时的逻辑，找出给定数量的因素。 有存在的任何算法，基于相同的
其实，我真正的问题是要找出否定的。的存在对于给定数量的因素..
因此，任何算法，请让我知道这个。
感谢。
其实，我真正的问题是要找出否定的。的存在对于给定数量的因素..
好了，这是不同的。让 N 是给定的数字。
如果 N = P1 ^ E1 * P2 ^ E2 * ...... * ^ PK EK ，其中每个 P 是一个素数，的因素，那么这个数 N 是（E1 + 1）*（E2 + 1）* ... *（ EK + 1）。更多关于此这里。
因此，就足以找到每个首要因素出现在其中的权力。例如：
在正给出的读取数
initial_n = N
num_factors = 1;
为（ⅰ= 2; I * I＆其中; = initial_n ++ⅰ）//每个编号i，直到给定数量的平方根
{
功率= 0; //想我出现在0电源
同时（N％我== 0）//虽然我们可以把N的我
{
N = N / I //把它，从而保证我们只检查主要因素
++动力//增加我出现在电源
}
num_factors = num_factors *（电源+ 1）//运用公式
}
如果（正→1）//会发生例如用于14 = 2 * 7
{
num_factors = num_factors * 2 // n是素数，它的实力只能是1，所以乘以2的因子数
}
例如，以 18 。 18 = 2 ^ 1 * 3 * 2 =＆GT;的因子数目=（1 + 1）*（2 + 1）= 6 。事实上， 6 的因素18 是 1，2，3，6，9， 18 。
下面是我的方法，描述并发表@Maciej方法之间的一个小的基准。他拥有的是更容易实现的优点，而我拥有的是更快，如果变化只遍历素数，因为我已经做了这个测试的好处是：
类节目
{
静态私有列表＆LT; INT＆GT;素数=新的名单，其中，INT＆GT;（）;
私有静态无效筛（）
{
布尔[] OK =新布尔[2000];
的for（int i = 2; I＆LT; 2000; ++ I）//素数可达2000（只需要多达开方的1 000 000实际上）
{
如果（OK！[我]）
{
primes.Add（ⅰ）;
对于（INT J =; J＆LT; 2000; J + = 1）
OK [J] =真;
}
}
}
私有静态诠释IVlad（INT N）
{
INT initial_n = N;
int的因素= 1;
对（INT I = 0;素数[I] *素数[1] - ; =正++ⅰ）
{
INT功率= 0;
而（initial_n％的素数[I] == 0）
{
initial_n / =素数[I]
++电源;
}
因素* =权力+ 1;
}
如果（initial_n→1）
{
因素* = 2;
}
返回的因素;
}
私有静态诠释马切伊（INT N）
{
int的因素= 1;
INT I = 2;
对于（; I * I n种; ++ I）
{
如果（N％我== 0）
{
++因素;
}
}
因素* = 2;
如果（I * I = = N）
{
++因素;
}
返回的因素;
}
静态无效的主要（）
{
筛（）;
Console.WriteLine（测试等价......）;
的for（int i = 2; I＆LT; 1000000; ++ I）
{
如果（马切伊（ⅰ）！= IVlad（i））的
{
Console.WriteLine（失败！）;
Environment.Exit（1）;
}
}
Console.WriteLine（等效确认！）;
Console.WriteLine（时序IVlad ......）;
秒表T =新的秒表（）;
t.Start（）;
的for（int i = 2; I＆LT; 1000000; ++ I）
{
IVlad（ⅰ）;
}
Console.WriteLine（总毫秒：{0}，t.ElapsedMilliseconds）;
Console.WriteLine（时序马切伊......）;
t.Reset（）;
t.Start（）;
的for（int i = 2; I＆LT; 1000000; ++ I）
{
马切伊（ⅰ）;
}
Console.WriteLine（总毫秒：{0}，t.ElapsedMilliseconds）;
}
}
结果我的机器上：
测试等价...
等价确认！
时序IVlad ...
总毫秒：2448
时序马切伊...
总毫秒：3951
preSS任意键继续。 。 。
What could be the simplest and time efficient logic to find out the factors of a given Number. Is there any algorithm that exist, based on the same.
Actually, my real problem is to find out the no. of factors that exist for a given Number..
So Any algorithm, please let me know on this..
Thanks.
Actually, my real problem is to find out the no. of factors that exist for a given Number..
Well, this is different. Let n be the given number.
If n = p1^e1 * p2^e2 * ... * pk^ek, where each p is a prime number, then the number of factors of n is (e1 + 1)*(e2 + 1)* ... *(ek + 1). More on this here.
Therefore, it is enough to find the powers at which each prime factor appears. For example:
read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
power = 0; // suppose the power i appears at is 0
while (n % i == 0) // while we can divide n by i
{
n = n / i // divide it, thus ensuring we'll only check prime factors
++power // increase the power i appears at
}
num_factors = num_factors * (power + 1) // apply the formula
}
if (n > 1) // will happen for example for 14 = 2 * 7
{
num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}
For example, take 18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. Indeed, the 6 factors of 18 are 1, 2, 3, 6, 9, 18.
Here's a little benchmark between my method and the method described and posted by @Maciej. His has the advantage of being easier to implement, while mine has the advantage of being faster if change to only iterate over the prime numbers, as I have done for this test:
class Program
{
static private List<int> primes = new List<int>();
private static void Sieve()
{
bool[] ok = new bool[2000];
for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually)
{
if (!ok[i])
{
primes.Add(i);
for (int j = i; j < 2000; j += i)
ok[j] = true;
}
}
}
private static int IVlad(int n)
{
int initial_n = n;
int factors = 1;
for (int i = 0; primes[i] * primes[i] <= n; ++i)
{
int power = 0;
while (initial_n % primes[i] == 0)
{
initial_n /= primes[i];
++power;
}
factors *= power + 1;
}
if (initial_n > 1)
{
factors *= 2;
}
return factors;
}
private static int Maciej(int n)
{
int factors = 1;
int i = 2;
for (; i * i < n; ++i)
{
if (n % i == 0)
{
++factors;
}
}
factors *= 2;
if (i * i == n)
{
++factors;
}
return factors;
}
static void Main()
{
Sieve();
Console.WriteLine("Testing equivalence...");
for (int i = 2; i < 1000000; ++i)
{
if (Maciej(i) != IVlad(i))
{
Console.WriteLine("Failed!");
Environment.Exit(1);
}
}
Console.WriteLine("Equivalence confirmed!");
Console.WriteLine("Timing IVlad...");
Stopwatch t = new Stopwatch();
t.Start();
for (int i = 2; i < 1000000; ++i)
{
IVlad(i);
}
Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
Console.WriteLine("Timing Maciej...");
t.Reset();
t.Start();
for (int i = 2; i < 1000000; ++i)
{
Maciej(i);
}
Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
}
}
Results on my machine:
Testing equivalence...
Equivalence confirmed!
Timing IVlad...
Total milliseconds: 2448
Timing Maciej...
Total milliseconds: 3951
Press any key to continue . . .
这篇关于算法找到给定数量..最短方法的因素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
