Vấn đề dự án Euler 12 - C++

Question

Tôi đang làm việc về vấn đề 12 liên quan đến số tam giác đầu tiên với 500 ước. Tôi đã cố gắng giải quyết vấn đề. Tôi nhận được 300 ước trong khoảng 35 giây và không thể nhận được 400 trong vòng 10 phút. Tôi sẽ thay đổi giải pháp của mình để sử dụng phương pháp hệ số nguyên tố nhưng bây giờ tôi đã thấy rằng mọi người vẫn nhận được giải pháp này với lực lượng vũ phu trong chưa đầy một phút.

Bạn có thể phê bình mã của tôi và cho tôi biết nếu tôi thiếu thứ gì đó đang làm cho điều này không hiệu quả khủng khiếp?

unsigned long long TriangleNumberDivisors(int divisorTarget) 
{ 
    unsigned long long triangleNum=1; 
     unsigned long long currentNum=2; 
    int numOfDivisors=0; 


    numOfDivisors=NumOfDivisors(triangleNum); 
    while(numOfDivisors<divisorTarget) 
    { 
     triangleNum+=currentNum; 
     currentNum++; 
     numOfDivisors=NumOfDivisors(triangleNum); 
    } 

    return triangleNum; 
} 

int NumOfDivisors(unsigned long long dividend) 
{ 
    int numDivisors=0; 
    set<unsigned long long> divisors; 
    set<unsigned long long>::iterator it; 

    for(unsigned long long index=1; index<=dividend/2; index++) 
    { 
     if(dividend%index==0) 
     { 
      divisors.insert(index); 
      numDivisors++; 
      it=divisors.find(dividend/index); 
      if(it==divisors.end()) 
      { 
       divisors.insert(dividend/index); 
       numDivisors++; 
      } 
       /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower 
      for(it=divisors.begin();it!=divisors.end();it++) 
      { 
        numDivisors++; 
      } 
        */ 
     } 
    } 

    return numDivisors; 
} 

int main() 
{ 
    cout<<TriangleNumberDivisors(500)<<endl; 

    return 0; 
} 

Cập nhật: Có ngay bây giờ, cảm ơn. Thay đổi để chỉ kiểm tra đến căn bậc hai của số, và đã làm một kiểm tra bổ sung để xem nếu nó là một hình vuông hoàn hảo. Điều này cho phép tôi xóa hoàn toàn bộ này. 500 divisors chạy trong 12 giây.

Answer 1

Bạn hiện đang kiểm tra ước tính lên đến dividend/2. Bạn có thể giảm số này xuống sqrt(dividend), nhanh hơn một cách tiệm cận. Một trường hợp đặc biệt có thể cần thiết nếu dividend là hình vuông.

C++ Mã của tôi cho vấn đề 12 (mà không cơ bản giống như bạn, nhưng sử dụng giới hạn dưới này, và cũng chỉ đếm ước chứ không phải lưu trữ chúng trong tập) mất khoảng 1 giây

Answer 2

for(unsigned long long index=1; index<=dividend/2; index++) 

tôi xem bạn đã cố gắng tối ưu hóa điều này bằng cách giới hạn vòng lặp của bạn thành dividend/2, thay vì lặp lại tất cả các cách đến dividend. Giới hạn bản thân ở số sqrt(dividend) sẽ tốt hơn (theo nghĩa là bạn đang kiểm tra số ít ước số hơn).

Ngoài ra, nếu bạn giới hạn mình bằng căn bậc hai của cổ tức, bạn không phải kiểm tra ước tính trùng lặp. Điều đó sẽ chỉ xảy ra cho số vuông, vì vậy chỉ cần kiểm tra xem index == cổ tức/chỉ mục, để tránh chèn trùng lặp.

Answer 3

Tôi không chắc chắn lý do bạn cần divisors, biến số set, theo phương pháp NumOfDivisors. Tại sao đếm numDivisors (với chỉ mục tối đa sqrt(dividend)) là không đủ? (set được thực hiện như một cây tìm kiếm nhị phân cân bằng, nó đang làm chậm phương thức.). Hơn nữa, có vẻ như bạn đang gọi divisors.insert(..)hai lần.

Answer 4

Có vẻ như bạn có thể đạt được một số hiệu suất nếu bạn đã lưu vào bộ nhớ số lượng ước cho một số cụ thể khi bạn đi cùng.