Алгоритм для нахождения всех точных делителей заданного целого числа

Ответ 1

Во-первых, ваш код должен иметь условие i <= n/2, иначе он может пропустить один из факторов, например, 6 не будет напечатано, если n = 12.

Запустите цикл с квадратным корнем из числа (т.е. i <= sqrt(n)) и напечатайте как i, так и n/i (оба будут кратными n).

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

Примечание:

• Для идеального квадрата, так что квадратный корень не печатается дважды, дополнительная проверка выполняется в конце цикла для i*i == n, как предложено @chepner.
• Если вы хотите, чтобы все факторы в порядке возрастания сохраняли значения в массиве, то в конце цикла сортировать все числа и отображать.

Ответ 2

Поиск всех делителей с помощью "нахождения всех простых факторов" в C (быстрее) и до 18 цифр.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) {
    unsigned int lastdiv = 0;
    divisors[lastdiv++] = 1;
    unsigned long long powerfactor = 1;
    unsigned long long number = N;
    while ((number & 1) == 0) {
        powerfactor <<= 1;
        divisors[lastdiv++] = powerfactor;
        number >>= 1;
    }

    unsigned long long factor = 3; unsigned long long upto = lastdiv;
    powerfactor = 1;
    while (factor * factor <= number) {
        if (number % factor == 0) {
            powerfactor *= factor;
            for (unsigned int i = 0; i < upto; i++)
                divisors[lastdiv++] = divisors[i] * powerfactor;
            number /= factor;
        }
        else {
            factor += 2; upto = lastdiv;
            powerfactor = 1;
        }
    }

    if (number > 1) {
        if (number != factor) {
            upto = lastdiv;
            powerfactor = 1;
        }
        powerfactor *= number;
        for (unsigned int i = 0; i < upto; i++)
            divisors[lastdiv++] = divisors[i] * powerfactor;
    }
    return lastdiv;
}

int cmp(const void *a, const void *b) {
    if( *(long long*)a-*(long long*)b < 0 ) return -1;
    if( *(long long*)a-*(long long*)b > 0 ) return 1;
    return 0;
}

int main(int argc, char *argv[]) {
    unsigned long long N = 2;
    unsigned int Ndigit = 1;
    if (argc > 1) {
        N = strtoull(argv[1], NULL, 10);
        Ndigit = strlen(argv[1]);
    }
    unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344,
                             2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680};

    unsigned long long divisors[maxdiv[Ndigit]];
    unsigned int size = FindDivisors(divisors, N);
    printf("Number of divisors = %u\n", size);

    qsort(divisors, size, sizeof(unsigned long long), cmp);
    for (unsigned int i = 0; i < size; i++)
        printf("%llu ", divisors[i]);
    printf("\n");

    return 0;
}

Ответ 3

Простой линейный поиск может быть улучшен путем первого выброса всех факторов 2. Это может быть сделано путем простого смещения битов или отсчета отсчета с хорошей внутренней функцией. Это очень быстро в любом случае. Затем запустите алгоритм, предложенный shg (который будет работать намного быстрее, если нет двух мощностей), и объедините результат со всеми возможными степенями двух (не забудьте этот шаг). Это помогает много для входов, у которых много тренировочных нолей, но даже помогает, если они этого не делают - вам больше не придется тестировать какие-либо четные делители, поэтому цикл становится вдвое длиннее.

Также могут помочь выброс некоторых постоянных низких факторов (но больше 2). Modulo с константой почти наверняка оптимизирован компилятором (или, если нет, вы можете сделать это самостоятельно), но что более важно, это означает, что осталось меньше делителей для тестирования. Не забудьте объединить этот фактор с найденными делителями.

Вы также можете факторизовать номер полностью (используйте ваш любимый алгоритм - возможно, Pollard Rho будет лучше), а затем распечатайте все продукты (за исключением пустого продукта и полного продукта) факторов. Это имеет хорошие шансы стать быстрее для больших вводов - алгоритм Полларда Ро обнаруживает факторы очень быстро по сравнению с простым линейным поиском, обычно меньше факторов, чем правильные делители, и последний шаг (перечисление продуктов) включает только быструю математику (без дивизий). Это в основном помогает для чисел с очень небольшими факторами, которые Rho находит наиболее быстрыми.

Ответ 4

В коде, представленном в одном из ответов, есть ошибка, которую трудно увидеть на первый взгляд. Если sqrt (n) является действительным делителем; но n не является идеальным квадратным числом, тогда два результата опущены.

например. Попробуйте n = 15 и посмотрите, что произойдет; sqrt(15) = 3, поэтому последнее значение цикла while равно 2. Следующий оператор, выполняемый if (i * i == n), будет выполнен как if(3 * 3 == 15). Таким образом, 3 не отображается в виде делителя, также было пропущено 5.

Ниже будет рассмотрен общий случай положительных целых чисел.

 {
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

Ответ 5

  int count = 2;
     //long childsum = 0;
           long _originalvalue = sum;
     dividend = "1";
     for (int i = 2; i < sum; i++)
     {
         if (_originalvalue % i == 0)
         {
             sum = _originalvalue / i;
             //sum = childsum;
             dividend = dividend + "," + i+","+sum;
             if (sum == i)
             {
                 count++;
             }
             else
             {
                 count = count + 2;
             }
         }
     }
     return count;

Ответ 6

Когда заданное число нечетно, мы можем даже пропустить четные числа. Небольшая импровизация в принятом коде:)

Здесь это код Java для нахождения факторов заданного числа.

import java.util.Scanner;
public class Factors {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-- > 0) {
            int n = scanner.nextInt();
            if(n % 2 == 0) {
                for(int i = 1; i <= Math.sqrt(n); i++) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
            else {
                for(int i = 1; i <= Math.sqrt(n); i=i+2) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
        }
    }
}

Ответ 7

Это моя новая версия С#. Благодаря Rndm он почти в 50 раз быстрее, чем моя первая попытка.

public static long GetDivisors(long number)
    {
        long divisors = 0;

        long boundary = (long)Math.Sqrt(number);

        for (int i = 1; i <= boundary; i++)
        {
            if (number % i == 0)
            {
                divisors++;
                if(i != (number / i))
                {
                    if (i * i != number)
                    {
                        divisors++;
                    }
                }
            }
        }

        return divisors;
    }