Алгоритм проверки, если число, если идеальное число - PullRequest
Новая
       22

Алгоритм проверки, если число, если идеальное число

6 голосов
/ 04 июля 2011

Я ищу алгоритм, чтобы найти, является ли данное число идеальным числом.

Самое простое, что приходит мне в голову:

  1. Найти все множители числа
  2. Получите простые факторы [кроме самого числа, если оно простое], и сложите их, чтобы проверить, является ли оно совершенным числом.

Есть ли лучший способ сделать это? При поиске, некоторые работы Евклида подошли, но не нашли никакого хорошего алгоритма. Также этот скрипт не помог: https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number.

Числа и т. Д. Могут кэшироваться и т. Д. При использовании в реальном мире [я не знаю, где используются совершенные nos:)]
Однако, поскольку об этом спрашивают в интервью, я предполагаю, что должен быть «производный» способ его оптимизации.

Спасибо!

Ответы [ 4 ]

9 голосов
/ 04 июля 2011

Если вход четный, посмотрите, имеет ли он форму 2^(p-1)*(2^p-1), с p и 2^p-1 штрих.

Если ввод нечетный, вернуть «false». : -)

Подробнее см. На странице Википедии .

(На самом деле, поскольку существует всего 47 совершенных чисел с числом менее 25 миллионов цифр, вы можете начать с простой таблицы таких. Спросите интервьюера, можете ли вы предположить, что вы используете, например, 64-разрядные числа ... )

0 голосов
/ 30 июля 2016 
#include<stdio.h>
#include<stdlib.h>
int sumOfFactors(int ); 

int main(){
int x, start, end;
    printf("Enter start of the range:\n");
    scanf("%d", &start);
    printf("Enter end of the range:\n");
    scanf("%d", &end);

    for(x = start;x <= end;x++){
        if(x == sumOfFactors(x)){
            printf("The numbers %d is a perfect number\n", x);
        }
    }   
    return 0;
}

int sumOfFactors(int x){
    int sum = 1, i, j;
    for(j=2;j <= x/2;j++){
        if(x % j == 0)
            sum += j;
    }
    return sum;
}
0 голосов
/ 04 июля 2011

Редактировать : Черт, Я провалил собеседование! : - (
В моей чрезмерной ревностной попытке найти трюки или эвристику, чтобы улучшить "разложить на множители + перечислить делители +"суммируя их, я не смог отметить, что быть 1 по модулю 9 было просто необходимым и, конечно, не достаточным условием для числа (кроме 6), чтобы быть идеальным ...
Ду ... со средним числом 1 из 9, удовлетворяющим этому условию, мой алгоритм наверняка найдет слишком много идеальных чисел; -).
Чтобы избавиться от себя, сохраняй и поддерживай предложение использоватьцифровой корень, но только в качестве фильтра , чтобы в большинстве случаев избежать более дорогостоящего вычисления коэффициента.

[Первоначальная попытка: Зал стыда] 

If the number is even,<br>
   compute its [digital root][1].
       if the digital root is 1, the number is perfect, otherwise it isn't.

If the number is odd...
   there are no shortcuts, other than...
       "Not perfect" if the number is smaller than 10^300
       For bigger values, one would then need to run the algorithm described in 
       the question, possibly with a few twists typically driven by heuristics
       that prove that the sum of divisors will be lacking when the number
       doesn't have some of the low prime factors.

Моя причина, по которой я предлагаю цифровой корневой трюк для четных чисел, заключается в том, что этот может быть вычислен без помощи арифметической библиотеки произвольной длины (например, GMP),Это также намного менее вычислительно дорого , чем разложение по простым факторам и / или факторизация (2 ^ (p-1) * ((2 ^ p) -1)).Поэтому, если интервьюер должен быть удовлетворен ответом «Нет идеального» для нечетных чисел, решение будет очень эффективным и кодируемым на большинстве компьютерных языков.

[Вторая и третья попытка ...] 

If the number is even,<br>
   if it is 6
      The number is PERFECT
   otherwise compute its [digital root][1].
       if the digital root is _not_ 1
           The number is NOT PERFECT
       else ..., 
           Compute the prime factors
           Enumerate the divisors, sum them
           if the sum of these divisor equals the 2 * the number
                it is PERFECT
           else
                it is NOT PERFECT

If the number is odd...
    same as previously

На этот относительно странный вопрос для интервью ... * Второй комментарий andrewdski к другому ответу в этом посте,что этот конкретный вопрос довольно странный в контексте интервью для разработчика общего назначения.
Как и во многих вопросах интервью, возможно, что интервьюер не ищет конкретного решения, а скорее предоставляет возможность длякандидат продемонстрировать свою способность сформулировать общие плюсы и минусы различных подходов.Кроме того, если кандидату предоставляется возможность поиска общих ресурсов, таких как MathWorld или Wikipedia, перед ответом, это также может быть хорошим тестом на его / ее способность быстро разобраться в информации, предлагаемой там.

0 голосов
/ 04 июля 2011

Вот быстрый алгоритм для удовольствия, в PHP - с использованием простого цикла for.Вы можете легко перенести это на другие языки: 

function isPerfectNumber($num) {
        $out = false;

        if($num%2 == 0) {
            $divisors = array(1);
            for($i=2; $i<$num; $i++) {
                if($num%$i == 0)
                    $divisors[] = $i;
            }

            if(array_sum($divisors) == $num)
                $out = true;
        }

        return $out ? 'It\'s perfect!' : 'Not a perfect number.';
    }

Надеюсь, это поможет, но не уверен, что это то, что вам нужно.

...