Điều với Project Euler là thường có một phương pháp brute-force rõ ràng để thực hiện vấn đề, điều này sẽ mất khoảng mãi mãi. Khi các câu hỏi trở nên khó khăn hơn, bạn sẽ cần phải thực hiện các giải pháp thông minh.
Một cách bạn có thể giải quyết vấn đề này là sử dụng vòng lặp luôn tìm thấy hệ số nhỏ nhất (số nguyên dương) của một số. Khi yếu tố nhỏ nhất của một con số là con số đó, thì bạn đã tìm ra nhân tố chính yếu nhất!
Chi tiết mô tả thuật toán:
Bạn có thể làm điều này bằng cách giữ ba biến:
Số bạn đang cố gắng yếu tố (A) Một cửa hàng ước hiện tại (B) Một cửa hàng ước lớn nhất (C)
Ban đầu, hãy để (A) là số bạn quan tâm - trong trường hợp này là 600851475143. Sau đó để (B) là 2. Có điều kiện kiểm tra nếu (A) chia hết cho (B) . Nếu nó chia hết, chia (A) bằng (B), đặt lại (B) thành 2, và quay trở lại để kiểm tra xem (A) có chia hết cho (B) hay không. Khác, nếu (A) không chia hết cho (B), số gia tăng (B) bằng +1 và sau đó kiểm tra xem (A) có chia hết cho (B) hay không. Chạy vòng lặp cho đến khi (A) là 1. (3) bạn trở lại sẽ là số nguyên tố lớn nhất của 600851475143.
Có rất nhiều cách bạn có thể làm điều này hiệu quả hơn - thay vì tăng đến số nguyên tiếp theo, bạn có thể tăng lên số nguyên nguyên nhất thiết tiếp theo, và thay vì giữ một kho số chia lớn nhất, bạn chỉ có thể trả về số hiện tại khi ước số duy nhất của nó là chính nó. Tuy nhiên, thuật toán tôi mô tả ở trên sẽ chạy trong vài giây bất kể.
Việc thực hiện trong python là như sau: -
def lpf(x):
lpf = 2;
while (x > lpf):
if (x%lpf==0):
x = x/lpf
lpf = 2
else:
lpf+=1;
print("Largest Prime Factor: %d" % (lpf));
def main():
x = long(raw_input("Input long int:"))
lpf(x);
return 0;
if __name__ == '__main__':
main()
Ví dụ: Hãy tìm ra thừa số nguyên tố lớn nhất của 105 sử dụng phương pháp mô tả ở trên.
Cho (A) = 105. (B) = 2 (chúng tôi luôn bắt đầu bằng 2) và chúng tôi chưa có giá trị cho (C).
Có (A) chia hết cho (B) không? Số Tăng (B) bằng +1: (B) = 3. Is Is (A) chia hết cho (B)? Vâng. (105/3 = 35). Ước số lớn nhất được tìm thấy cho đến nay là 3. Hãy (C) = 3. Cập nhật (A) = 35. Đặt lại (B) = 2.
Bây giờ, (A) chia hết cho (B)? Số Tăng (B) +1: (B) = 3. Có (A) chia hết cho (B)? Số Tăng (B) bằng +1: (B) = 4. Có (A) chia hết cho (B)? Số tăng (B) +1: (B) = 5. Có (A) chia hết cho (B)? Vâng. (35/5 = 7). Ước số lớn nhất mà chúng tôi đã tìm thấy trước đó được lưu trữ trong (C). (C) hiện tại 3. 5 lớn hơn 3, vì vậy chúng tôi cập nhật (C) = 5. Chúng tôi cập nhật (A) = 7. Chúng tôi thiết lập lại (B) = 2. Sau đó chúng ta lặp lại quá trình cho (A), nhưng chúng ta sẽ tiếp tục tăng (B) cho đến khi (B) = (A), bởi vì 7 là số nguyên tố và không có ước số nào ngoài chính nó và 1. (Chúng ta đã có thể dừng khi (B)> ((A)/2), vì bạn không thể có ước số nguyên lớn hơn một nửa số - ước số nhỏ nhất có thể (trừ 1) của bất kỳ số nào là 2!)
Vì vậy điểm chúng tôi trở lại (A) = 7.
Hãy thử thực hiện một vài thao tác này một cách thủ công và bạn sẽ nhận được ý tưởng
Tôi muốn xem việc triển khai hàm 'notPrime()' huyền diệu của bạn. :) –
heh, thật dễ dàng: notPrime (n) = (getLowestDivisiblePrimeNumber (n) == n). –
Thành thật mà nói, tôi sử dụng trong khi (đúng) ở đó, nó chỉ là dễ dàng hơn để giải thích theo cách này. Phương thức getLowestDivisiblePrime của tôi đề cập đến danh sách chính ArrayList; Nếu không có số nguyên tố divisible trong primList, nó sẽ tìm số nguyên tố tiếp theo để thêm vào primList và tiếp tục làm như vậy cho đến khi tìm thấy số nguyên tố 'số' chia hết cho (và sau đó sẽ tham chiếu đến danh sách số nguyên tố lớn hơn) , hoặc cho đến khi số nguyên tố lớn nhất trong danh sách chính lớn hơn sqaureroot của 'số'. Không có phép thuật ở đó, mặc dù tôi hy vọng nó khá hiệu quả. = P –
Jonathan