Лучший способ найти все факторы данного числа
Исключение нулевого указателя - это индикатор того, что вы используете объект, не инициализируя его.
Например, ниже - класс ученика, который будет использовать его в нашем коде.
public class Student {
private int id;
public int getId() {
return this.id;
}
public setId(int newId) {
this.id = newId;
}
}
Приведенный ниже код дает вам исключение с нулевым указателем.
public class School {
Student obj_Student;
public School() {
try {
obj_Student.getId();
}
catch(Exception e) {
System.out.println("Null Pointer ");
}
}
}
Поскольку вы используете Obj_Student, но вы забыли инициализировать его, как в правильном коде, показанном ниже:
public class School {
Student obj_Student;
public School() {
try {
obj_Student = new Student();
obj_Student.setId(12);
obj_Student.getId();
}
catch(Exception e) {
System.out.println("Null Pointer ");
}
}
}
8 ответов
псевдокод:
- Цикл от 1 до квадратного корня числа, назовите индекс "i".
- , если модификация числа, которая я 0, добавляем я и число / я к списку факторов.
realocode:
public List<int> Factor(int number) {
List<int> factors = new List<int>();
int max = (int)Math.Sqrt(number); //round down
for(int factor = 1; factor <= max; ++factor) { //test from 1 to the square root, or the int below it, inclusive.
if(number % factor == 0) {
factors.Add(factor);
if(factor != number/factor) { // Don't add the square root twice! Thanks Jon
factors.Add(number/factor);
}
}
}
return factors;
}
, Поскольку Jon Skeet упомянул, Вы могли реализовать это как IEnumerable<int> также - использование урожай вместо того, чтобы добавить к списку. Преимущество с List<int> состоит в том, что это могло быть отсортировано перед возвратом при необходимости. С другой стороны Вы могли получить отсортированный перечислитель с гибридным подходом, приведя к первому фактору и храня второй в каждом повторении цикла, затем приведя к каждому значению, которое было сохранено в обратном порядке.
Вы также захотите сделать что-то для обработки случая, куда отрицательное число передало в функцию.
% (остаток) оператор является тем для использования здесь. Если x % y == 0 тогда x является делимым y. (Принятие 0 < y <= x)
я лично реализовал бы это как метод, возвратившись IEnumerable<int> использование блока итератора.
Как дополнительные методы:
public static bool Divides(this int potentialFactor, int i)
{
return i % potentialFactor == 0;
}
public static IEnumerable<int> Factors(this int i)
{
return from potentialFactor in Enumerable.Range(1, i)
where potentialFactor.Divides(i)
select potentialFactor;
}
Вот пример использования:
foreach (int i in 4.Factors())
{
Console.WriteLine(i);
}
Примечание, которое я оптимизировал для ясности, не для производительности. Для больших значений i может занять много времени этот алгоритм.
Здесь это снова, только рассчитывает к квадратному корню как другие упомянутый. Я предполагаю, что люди притягиваются к той идее, если Вы надеетесь улучшить производительность. Я записал бы изящный код сначала и оптимизировал бы для производительности позже после тестирования моего программного обеспечения.
однако, для ссылки, здесь это:
public static bool Divides(this int potentialFactor, int i)
{
return i % potentialFactor == 0;
}
public static IEnumerable<int> Factors(this int i)
{
foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i))
where potentialFactor.Divides(i)
select potentialFactor)
{
yield return result;
if (i / result != result)
{
yield return i / result;
}
}
}
Не только результат, значительно менее читаемый, но и факторы прибывают не в порядке этот путь, также.
Другой стиль LINQ и связывающий для хранения O (sqrt (n)) сложностью
static IEnumerable<int> GetFactors(int n)
{
Debug.Assert(n >= 1);
var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1)))
where n % i == 0
select new { A = i, B = n / i };
foreach(var pair in pairList)
{
yield return pair.A;
yield return pair.B;
}
}
Также не имело бы смысла запускаться в 2 и направляться к значению верхнего предела, это непрерывно повторно вычисляется на основе числа, которое Вы только что проверили? См. N/i (где N является Число, Вы пытаетесь найти фактор, и я - текущее число для проверки...), Идеально, вместо модификации, Вы использовали бы функцию деления, которая возвращает N/i, а также любой остаток, который это могло бы иметь. Тем путем Вы выполняете, каждый делит операцию для воссоздания верхней границы, а также остатка, который Вы проверите на даже подразделение.
Математика. DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx
Решение Linq:
IEnumerable<int> GetFactors(int n)
{
Debug.Assert(n >= 1);
return from i in Enumerable.Range(1, n)
where n % i == 0
select i;
}
Очень поздно, но принятый ответ (некоторое время назад) не дал правильных результатов.
Благодаря Мерлину, я теперь понял причину квадрата как «максимум» под исправленным образцом. хотя ответ от Echostorm кажется более полным.
public static IEnumerable<uint> getFactors(uint x)
{
for (uint i = 1; i*i <= x; i++)
{
if (0 == (x % i))
{
yield return i;
if (i != (x / i))
{
yield return x / i;
}
}
}
}