На самом деле, моя настоящая проблема - найти нет.факторов, которые существуют для данного числа ..
Ну, это другое.Пусть n будет заданным числом.
Если n = p1^e1 * p2^e2 * ... * pk^ek, где каждое p - простое число, то число факторов n равно (e1 + 1)*(e2 + 1)* ... *(ek + 1).Подробнее об этом здесь .
Таким образом, достаточно найти силы, при которых появляется каждый главный фактор.Например:
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
}
Например, взять 18.18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6.Действительно, 6 факторы 18 равны 1, 2, 3, 6, 9, 18.
Вот небольшой тест между моим методом и методом, описанным и опубликованным @Maciej.Его преимущество в том, что его легче реализовать, а в моем - преимущество в том, чтобы быстрее выполнять изменения, чтобы перебирать только простые числа, как я сделал для этого теста:
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);
}
}
Результаты на моей машине:
Проверка эквивалентности ...
Эквивалентность подтверждена!
Сроки IVlad ...
Всего миллисекунд: 2448
Время Maciej ...
Всего миллисекунд: 3951
Нажмите любую клавишу для продолжения.,,