Lấy các yếu tố của một số

Question

Vấn đề: Tôi đang cố gắng refactor thuật toán này để làm cho nó nhanh hơn. Điều gì sẽ là refactoring đầu tiên ở đây cho tốc độ?

public int GetHowManyFactors(int numberToCheck) 
    { 
     // we know 1 is a factor and the numberToCheck 
     int factorCount = 2; 
     // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor 
     for (int i = 2; i < numberToCheck; i++) 
     { 
      if (numberToCheck % i == 0) 
       factorCount++; 
     } 
     return factorCount; 
    } 

Answer 1

Tối ưu hóa đầu tiên bạn có thể thực hiện là bạn chỉ cần kiểm tra căn bậc hai của số. Điều này là bởi vì các yếu tố đi theo cặp trong đó một phần nhỏ hơn căn bậc hai và cái kia lớn hơn.

Một ngoại lệ cho điều này là nếu n là hình vuông chính xác thì căn bậc hai của nó là hệ số của n nhưng không phải là một phần của một cặp.

Ví dụ, nếu số của bạn là 30 yếu tố trong những cặp:

• 1 x 30
• 2 x 15
• 3 x 10
• 5 x 6

Vì vậy, bạn không cần phải kiểm tra bất kỳ số nào cao hơn 5 vì tất cả các yếu tố khác có thể đã được suy ra để tồn tại khi bạn tìm thấy yếu tố nhỏ tương ứng trong cặp.

Dưới đây là một cách để làm điều đó trong C#:

public int GetFactorCount(int numberToCheck) 
{ 
    int factorCount = 0; 
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck)); 

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1. 
    for (int i = 1; i < sqrt; i++) 
    { 
     if (numberToCheck % i == 0) 
     { 
      factorCount += 2; // We found a pair of factors. 
     } 
    } 

    // Check if our number is an exact square. 
    if (sqrt * sqrt == numberToCheck) 
    { 
     factorCount++; 
    } 

    return factorCount; 
} 

Có phương pháp khác mà bạn có thể sử dụng được nhanh hơn nhưng bạn có thể thấy rằng đây là đã đủ nhanh cho các nhu cầu của bạn, đặc biệt nếu bạn chỉ cần nó hoạt động với các số nguyên 32 bit.

Answer 2

Giảm ràng buộc cao như thế nào bạn phải đi như bạn cố ý có thể dừng lại ở căn bậc hai của số lượng, mặc dù điều này không thực hiện sự thận trọng của chọn ra hình vuông mà có thể có các số lẻ của các yếu tố, nhưng nó giúp giảm tần suất vòng lặp phải được thực thi.

Answer 3

1. Bạn có thể giới hạn giới hạn trên của vòng lặp CHO bạn để numberToCheck/2

2. Bắt đầu vòng lặp truy cập của bạn ở mức 2 (nếu số của bạn là chẵn) hoặc 3 (cho các giá trị lẻ). Điều này sẽ cho phép bạn kiểm tra mọi số khác giảm số vòng lặp của bạn thêm 50% nữa.

   public int GetHowManyFactors(int numberToCheck) 
   { 
       // we know 1 is a factor and the numberToCheck 
       int factorCount = 2; 
   
       int i = 2 + (numberToCheck % 2); //start at 2 (or 3 if numberToCheck is odd) 
   
       for(; i < numberToCheck/2; i+=2) 
       { 
       if (numberToCheck % i == 0) 
        factorCount++; 
       } 
       return factorCount; 
   } 
   

Answer 4

Hình như có một cuộc thảo luận dài về chủ đề này chính xác ở đây: Algorithm to calculate the number of divisors of a given number

Hope this helps

Answer 5

Vâng, nếu bạn đang đi để sử dụng chức năng này rất nhiều, bạn có thể sử dụng được sửa đổi thuật toán của Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes và lưu trữ các câu trả lời trong khoảng từ 1 đến Max trong mảng. Nó sẽ chạy IntializeArray() một lần và sau khi nó sẽ trả về các câu trả lời trong 0 (1).

const int Max =1000000; 
int arr [] = new int [Max+1]; 

public void InitializeArray() 
{ 
    for(int i=1;i<=Max;++i) 
     arr[i]=1;//1 is factor for everyone 

    for(int i=2;i<=Max;++i) 
     for(int j=i;i<=Max;i+=j) 
      ++arr[j]; 
} 
public int GetHowManyFactors(int numberToCheck) 
{ 
    return arr[numberToCheck]; 
} 

Nhưng nếu bạn không sử dụng chức năng này, tôi nghĩ giải pháp tốt nhất là kiểm tra căn bậc hai.

---

Lưu ý: Tôi đã sửa mã của mình!

Answer 6

Điều đầu tiên cần lưu ý là nó đủ để tìm tất cả các yếu tố chính. Một khi bạn có những điều này thật dễ dàng để tìm số tổng số ước: cho mỗi số nguyên tố, thêm 1 vào số lần nó xuất hiện và nhân chúng lại với nhau. Vì vậy, đối với 12 = 2 * 2 * 3 bạn có (2 + 1) * (1 + 1) = 3 * 2 = 6 yếu tố.

Điều tiếp theo sau từ trường hợp đầu tiên: khi bạn tìm thấy một yếu tố, hãy chia nó ra sao cho số kết quả nhỏ hơn. Khi bạn kết hợp điều này với thực tế là bạn chỉ cần kiểm tra căn bậc hai của số hiện tại thì đây là một cải tiến lớn. Ví dụ, hãy xem xét N = 10714293844487412. Naively nó sẽ mất N bước. Kiểm tra đến căn bậc hai của nó có sqrt (N) hoặc khoảng 100 triệu bước. Nhưng vì các yếu tố 2, 2, 3 và 953 được phát hiện sớm trên thực tế bạn chỉ cần kiểm tra một triệu - một cải tiến 100x!

Cải thiện khác: bạn không cần phải kiểm tra mọi số để xem liệu số đó có chia số của bạn hay không, chỉ là số nguyên tố. Nếu nó thuận tiện hơn, bạn có thể sử dụng 2 và các số lẻ, hoặc 2, 3, và các số 6n-1 và 6n + 1 (một rây bánh xe cơ bản).

Đây là một cải tiến tốt đẹp khác. Nếu bạn có thể nhanh chóng xác định xem một số có phải là số nguyên tố hay không, bạn có thể giảm nhu cầu phân chia hơn nữa. Giả sử, sau khi loại bỏ các yếu tố nhỏ, bạn có 120528291333090808192969. Ngay cả khi kiểm tra đến căn bậc hai của nó sẽ mất một thời gian dài - 300 tỷ bước. Nhưng một thử nghiệm Miller-Rabin (rất nhanh - có thể 10 đến 20 nano giây) sẽ cho thấy rằng số này là tổng hợp. Điều này giúp ích như thế nào? Nó có nghĩa là nếu bạn kiểm tra căn bậc hai của nó và tìm thấy không có yếu tố, sau đó có chính xác hai số nguyên tố còn lại. Nếu số là một hình vuông, các nhân tố của nó là số nguyên tố; nếu số không phải là một hình vuông, các con số là số nguyên tố riêng biệt. Điều này có nghĩa là bạn có thể nhân số 'tổng chạy' của bạn bằng 3 hoặc 4, tương ứng, để có được câu trả lời cuối cùng - ngay cả khi không biết các yếu tố! Điều này có thể tạo ra nhiều sự khác biệt hơn bạn dự đoán: số bước cần thiết giảm từ 300 tỷ xuống chỉ còn 50 triệu, cải thiện gấp 6000 lần!

Vấn đề duy nhất với điều trên là Miller-Rabin chỉ có thể chứng minh rằng các số đó là tổng hợp; nếu nó được đưa ra một nguyên tố, nó không thể chứng minh rằng số đó là số nguyên tố. Trong trường hợp đó, bạn có thể viết một chức năng chứng minh nguyên thủy để tha cho chính mình những nỗ lực của bao thanh toán đến căn bậc hai của số. (Thay vào đó, bạn chỉ có thể thực hiện thêm một vài bài kiểm tra Miller-Rabin, nếu bạn hài lòng với độ tin cậy cao là câu trả lời của bạn đúng hơn là một bằng chứng cho nó. . trong một tỷ đồng)

Answer 7

An dễ dàng để thực hiện thuật toán đó sẽ mang lại cho bạn xa hơn nhiều so với bộ phận thử nghiệm được Pollard Rho

đây là một thực hiện Java, bạn cần phải dễ thích ứng với C#: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html

Answer 8

https://codility.com/demo/results/demoAAW2WH-MGF/

public int solution(int n) { 
     var counter = 0;   
     if (n == 1) return 1; 
     counter = 2; //1 and itself  
     int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n))); 
     for (int i = 2; i <= sqrtPoint; i++) 
     { 
     if (n % i == 0) 
     { 
      counter += 2; // We found a pair of factors.   
     }  
     } 
     // Check if our number is an exact square. 
     if (sqrtPoint * sqrtPoint == n) 
     { 
     counter -=1; 
     } 

     return counter; 
    }