Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: giúp mình với: Tìm n<10000 sao cho tổng các ước số nguyên tố của n là lớn nhất

  1. #1
    Ngày gia nhập
    02 2012
    Nơi ở
    q12
    Bài viết
    0

    Exclamation giúp mình với: Tìm n<10000 sao cho tổng các ước số nguyên tố của n là lớn nhất

    Không biết bài này sai ở đâu mà mình làm nó không cho kết quả.
    Code:
    #include <iostream.h>
    #include <math.h>
    #define GH 10000
    bool isPrime(unsigned long);
    int main(int argc, char *argv[])
    {
    	int i,j,k;
    	unsigned long s=0,max=0;
    	for(i=2;i<GH;i++)
    	{
    		for(j=1;j<i;j++)
    		{
    			if(isPrime(j)&&(i%j==0)) s+=j;
    		}
    		if(max<s) k=i;
    	}
    	cout<<"N ="<<k;
    	return 0;
    }
    bool isPrime(unsigned long num )
    {
    	int i,n;
    	bool flag=false;
    	n=num;
    	if (n<3&&n>0) return true;
    	else
    	{
    		i=2;
    		while((flag==false)&&(i<n))
    		{
    			if(n%i==0) flag=true;
    			else i++;
    		}
    		if (flag) return false;
    		else return true;
    	}
    }

  2. #2
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    Tổng các thừa số nguyên tố trong phân tích của số x có thể tìm trong O(logn).

    Với n < 10^4 bạn có thể for x in [1, n] , với mỗi x tính tổng thừa số ng tố rồi cập nhật max value, làm trong O(nlogn).

    Tuy nhiên nếu x là số tự nhiên và k là số nguyên tố thì y = x*k chắc chắn cho kết quả lớn hơn. Như vậy, bạn có thể for ngược từ n về 1, trong quá trình tách thừa số đánh dấu lại các số có dạng x / k với k là số nguyên tố. Các số được đánh dấu sẽ không cần xét lại. Độ phức tạp vẫn là O(nlogn) nhưng thực tế nhanh hơn nhiều.
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

  3. #3
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Không cho ra kết qủa là phải rồi, theo như trong code thì phải kiểm tra số nguyên tố tới 5000000 lần cơ mà.
    Bây giờ ở cái chỗ điều kiện ấy đổi chỗ 2 cái lại thì chương trình sẽ chạy nhanh hơn chút đấy, nhưng vẫn không đảm bảo là sẽ ra được kết quả trong thời gian gian chấp nhận được.

    Bây giờ làm thế này:
    - Cải tiến cách tính tổng các ước nguyên tố: lần lượt tìm các ước nguyên tố bằng phương pháp thử chia rồi cộng lại, trong diễn đàn đã có nhiều code của bài rồi. Tìm mấy bài phân tích thứa số nguyên tố là thấy.
    - Giảm số lần tính tổng: số dạng a*b chắc chắn có tổng các ước nguyên tố lớn hơn hoặc bằng tổng các ước nguyên tố của a và b. Như vậy số cần tìm sẽ nằm trong đoạn từ 5000 đến 9999.

  4. #4
    Ngày gia nhập
    02 2012
    Nơi ở
    q12
    Bài viết
    0

    cảm ơn đã gọi ý. nhưng vẫn chưa hiểu cho lắm. bài này dwarfboy93 vẫn xoay lui tới hoài về cách tính vét cạn
    hk bít còn cách nào giúp giảm bớt gánh nặng cho vòng lặp hk. mong các huynh chỉ giáo.

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Ko thích vét cạn ? Có 1 cách rất hay, độ phức tạp O(1). Bấm cái là ra

    Muốn biết cách này? Đầu tiên bạn phải cho mình biết là bạn đã nắm cách vét cạn thấu đáo rồi. Bấm chương trình cho chạy rồi in ra kết quả đúng. Chụp màn hình kết quả lên đây

    Rồi sau đó mình bày cách cho không vét cạn
    Um Mani Padme Hum...!!

  6. #6
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    140

    Mặc định giúp mình với: Tìm n<10000 sao cho tổng các ước số nguyên tố của n là lớn nhất

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Ko thích vét cạn ? Có 1 cách rất hay, độ phức tạp O(1). Bấm cái là ra

    Muốn biết cách này? Đầu tiên bạn phải cho mình biết là bạn đã nắm cách vét cạn thấu đáo rồi. Bấm chương trình cho chạy rồi in ra kết quả đúng. Chụp màn hình kết quả lên đây

    Rồi sau đó mình bày cách cho không vét cạn
    Làm bằng tay (cách nào hok biết). Xong viết chương trình cout kết quả

    Haaa, đùa tí. Sao không tìm hết số nguyên tố rồi lần ra kết quả trên tập số nguyên tố đó.
    Rẹt rẹt..

  7. #7
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi sim Xem bài viết
    Haaa, đùa tí. Sao không tìm hết số nguyên tố rồi lần ra kết quả trên tập số nguyên tố đó.
    Cách rất hay. Dựa vào đó ta có thể tìm ra kết quả của bài này là 9973, số nguyên tố lớn nhất nhỏ hơn 10000.

    Gọi hàm tổng các số nguyên tố của x là F(x)
    Giả sử số cần tìm có phân tích thừa số nguyên tố là x0 = p0^k0 * p1^k1 * p2^k2 * ... * pn^kn.
    Khi đó: x1 = p0 * p1 * p2 * ... * pn sẽ có F(x0) == F(x1)
    Như vậy ta chỉ cần xét trong các số có dạng x1 (tức là dạng tích của các số nguyên tố khác nhau như x1 là có thể tìm được số có F(x) lớn nhất).
    Xét số p = 9973 (số nguyên tố lớn nhất nhỏ hơn 10000). F(p) = p = 9973
    - Với các số x1 < 9973, ta có x1 = p0 * p1 * p2 * ... * pn < 9973 => p0 + p1 + p2 + ... + pn < 9973 (Do pi luôn lớn hơn hoặc bằng 2).
    - Với các số 1000 > x1 > 9973, x1 = p0 * a , p0 là ước nguyên tố nhỏ nhất của x1 (=> p0 < sqrt(x1) < 100) , a > 1
    Vi p0 >= 2 => a < 5000 => F(x1) <= p0 + a < 100 + 5000 < 9973

    Như vậy 9973 là số cần tìm.

    Với một giới hạn đủ lớn bất kỳ ta vẫn có thể làm tương tự như trên, khỏi cần vét cạn này nọ mất công.
    Đã được chỉnh sửa lần cuối bởi boss14420 : 03-03-2012 lúc 01:57 AM.

  8. #8
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Vậy sẽ phát sinh 1 lý thuyết :
    Tìm số n<Limit sao cho ...blah blah. :

    Gọi maxnto là số nguyên tố lớn nhấn <Limit
    Thì ta chỉ cần xét cho không gian từ maxnto đến Limit là sẽ tìm được đáp án

    Bởi vì giả sử Đáp án là 1 số k < maxnto thì nảy sinh 2 trường hợp:
    1- Số đó là số nguyên tố : Vậy sẽ mâu thuẫn bởi vì số đó < maxnto nên loại
    2- Số đó không phải là số nguyên tố: <-- Chứng minh tổng ước của chúng sẽ < maxnto để loại bỏ trường hợp này

    Vậy đỡ mất công vét cạn.

    Còn trong đoạn từ [maxnto , Limit) thì chưa biết.

    Với mỗi số i thuộc khoảng (maxnto,Limit) . Ta tìm trong tập các số nguyên tố [nto1,nto2,...,nton=maxnto] sao cho có tổ hợp nào mà tích của chúng >maxnto và <limit .
    Thử theo phương pháp giảm dần khung trượt từ limit về maxnto (tương ứng tổ hợp sẽ bắt đầu giảm từ maxnto...i , nto(n-1) ,...i vân vân) thì sẽ nhanh chóng tìm được đáp án. Tìm ra được tổ hợp số nào đầu tiên thỏa mãn điều kiện đó là hốt ra làm đáp án luôn.
    Đã được chỉnh sửa lần cuối bởi clchicken : 03-03-2012 lúc 12:16 PM.
    Um Mani Padme Hum...!!

  9. #9
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    140

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Tìm ra được tổ hợp số nào đầu tiên thỏa mãn điều kiện đó là hốt ra làm đáp án luôn.
    Chủ thread vô xem "hốt" đáp án được chưa
    Rẹt rẹt..

  10. #10
    Ngày gia nhập
    02 2012
    Nơi ở
    q12
    Bài viết
    0

    Hình như mấy bro nhầm ở đâu rồi. bài này kiểm tra xem số nào có tổng các ước số nhiều nhất mà mỗi ước số là số nguyên tố. chứ k phải tìm số nguyên tố cuối cùng đâu. vì số nguyên tố cuối cùng trong dãy đó là 9973 như các bro nêu trên.

Các đề tài tương tự

  1. Hỏi ý tưởng bài toán kết các tờ tiền định giá 100, 200, 500 thành 10000
    Gửi bởi boydamtac199 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 08-12-2013, 11:21 PM
  2. Vẽ 10000 sao nhấp nháy sử dụng OpenGL trong C/C++?
    Gửi bởi regulus trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 16-03-2011, 11:58 AM
  3. 1+2+3+4+...+n>10000
    Gửi bởi cutbo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 11-12-2009, 08:25 AM
  4. Tính 10000!
    Gửi bởi hirosama trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 12
    Bài viết cuối: 16-03-2009, 10:33 PM
  5. Diễn đàn sắp được 10000 đề tài rồi anh em có gì lên tiếng xem
    Gửi bởi AdminPro trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 6
    Bài viết cuối: 13-03-2009, 02:04 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn