Thuật toán để kiểm tra xem một số có phải là số hoàn hảo

Question

Tôi đang tìm một thuật toán để tìm số liệu đã cho có phải là số hoàn hảo hay không.

Các đơn giản nhất mà nói đến cái tâm của tôi là:

1. Tìm tất cả các yếu tố của số
2. Lấy thừa số nguyên tố [ngoại trừ số chính nó, nếu nó là số nguyên tố] và thêm họ lên kiểm tra nếu nó là một số hoàn hảo.

Có cách nào tốt hơn để thực hiện việc này không? Khi tìm kiếm, một số công trình Euclids đã xuất hiện, nhưng không tìm thấy bất kỳ thuật toán tốt nào. Ngoài ra golfscript này không hữu ích: https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number.

Các số vv có thể được lưu trong bộ nhớ cache, vv ..
Tuy nhiên, vì điều này đang được hỏi trong các cuộc phỏng vấn, tôi giả định rằng nên có một "có thể phát sinh" cách tối ưu hóa nó.

Cảm ơn!

Answer 1

Nếu đầu vào là số chẵn, hãy xem nó có ở dạng 2^(p-1)*(2^p-1), với p và 2^p-1 chính.

Nếu đầu vào là số lẻ, trả về "false". :-)

Xem chi tiết Wikipedia page.

(Thực tế, vì chỉ có 47 số hoàn hảo với ít hơn 25 triệu chữ số, bạn có thể bắt đầu bằng một bảng đơn giản. Hãy hỏi người phỏng vấn nếu bạn có thể giả sử bạn đang sử dụng số 64 bit, ví dụ .. .)

Answer 2

Đây là thuật toán nhanh chỉ để giải trí, bằng PHP - chỉ sử dụng vòng lặp for đơn giản. Bạn có thể easliy cổng đến các ngôn ngữ khác:

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.'; 
    } 

Hy vọng điều này sẽ giúp, không chắc chắn nếu đây là những gì bạn đang tìm kiếm.

Answer 3

Chỉnh sửa: Dang, Tôi đã thất bại trong cuộc phỏng vấn! :-(
Trong nỗ lực hết sức sốt sắng của tôi khi tìm kiếm thủ thuật hoặc chẩn đoán để cải thiện phương pháp "factorize + enumerate divisors + sum them", tôi không lưu ý rằng 1 modulo 9 chỉ là cần thiết và chắc chắn không a đủ điều kiện cho số (không phải 6) là hoàn hảo ...
Duh ... với số trung bình 1 trong 9 thậm chí số thỏa mãn điều kiện này, thuật toán của tôi chắc chắn sẽ tìm thấy một số quá hoàn hảo;).
Để tự đổi, duy trì và duy trì đề xuất sử dụng gốc kỹ thuật số, nhưng chỉ làm bộ lọc, để tránh tính toán yếu tố đắt tiền hơn, trong hầu hết các trường hợp.

---

[Original nỗ lực: hội trường của sự xấu hổ]

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. 

lý do của tôi cho thấy các trick gốc kỹ thuật số cho các số chẵn là này có thể được tính mà không cần sự giúp đỡ của một chiều dài tùy ý thư viện số học (như GMP). Nó cũng là ít tốn kém hơn nhiều tính toán so với sự phân hủy trong các hệ số nguyên tố và/hoặc hệ số hóa (2^(p-1) * ((2^p) -1)).   Do đó, nếu người phỏng vấn hài lòng với câu trả lời "Không hoàn hảo" cho số lẻ, giải pháp sẽ rất hiệu quả và có thể mã hóa được bằng hầu hết các ngôn ngữ máy tính.

---

[Thứ hai và thứ ba nỗ lực ...]

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 

---

Về câu hỏi phỏng vấn tương đối kỳ lạ này ...
Tôi thứ hai andrewdski 's bình luận cho câu trả lời khác trong bài đăng này, câu hỏi cụ thể này khá kỳ quặc trong bối cảnh cuộc phỏng vấn cho một nhà phát triển có mục đích chung.
Như với nhiều câu hỏi phỏng vấn, có thể người phỏng vấn không tìm kiếm một giải pháp cụ thể, mà là cung cấp cơ hội cho ứng cử viên thể hiện khả năng của mình để nói lên những ưu và khuyết điểm chung của các cách tiếp cận khác nhau. Ngoài ra, nếu ứng cử viên được cung cấp một cơ hội để tìm kiếm các tài nguyên chung như MathWorld hoặc Wikipedia trước khi trả lời, đây cũng có thể là một thử nghiệm tốt về khả năng của mình để nhanh chóng hiểu được thông tin được cung cấp ở đó.

Answer 4

#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; 
}