trận thách đấu mới Quanghero100 và Love_minh95

[11thanhkhoeo]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Thể theo nhu cầu chiến tranh đang dâng cao của 2 chú. Anh 11thanhkhoeo xin tổ chức võ đài để các chú chém code cho đã

Trận đấu có thể lệ như sau:

Quanghero100 và Love_minh95 Sẽ có một ngày để ra đề, 1 ngày viết code của bạn và ngày cuối cùng sẽ póst code đáp án. Đề bài, lời giải, đáp án sẽ được póst tại đây. Các chú có thể nhận thua, hoặc anh sẽ làm trọng tài. Nếu bất phân thắng bại, 11thanhkhoeo sẽ ra thêm 1 bài toán sau đó cả 2 cùng giải để phân định thắng bại

Các em có thể hẹn nhau ở đây thống nhất ngày ra đề, vì cũng sắp nghỉ hè hy vọng Anh sẽ được chứng kiến trận tranh tài này sớm

Thân

Mr favourite

11thanhkhoeo

 

[love_minh95]

thui được để em ra đề trước nhá

Cho dãy số a1,a2,a3,...,an đều là các số nguyên dương<=10^8, n<=100000.Do nghiện game,một hôm công bật máy tính lên để chơi game và chát linh tinh lên facebook đủ kiểu,nhưng không may máy bị bố khóa mã số,và máy không có bản ghost lên anh rất tức giận.Ông bố của anh gợi ý mã là số lượng số nguyên tố của dãy trên...máy tính phụ của anh ram 512mb nên khó có thể chạy đến 10^5,nhưng với thuật toán tốt thì có thể lắm.Vậy làm thế nào để tìm lại mật khẩu?
vào file Inp.text
dòng đầu là số n, (n<=100000);
dòng sau là a[1],a[2],....a[n]
ra file Out.text
số số nguyên tố trong dãy
&gt;-&gt;-&gt;-

 

[quanghero100]

uses crt;
var f:text;
    n,i,d:longint;
    a:array[1..100000] of longint;

function kt(n:longint):boolean;
var i:longint;
begin
   kt:=true;
   if n=2 then kt:=true
   else
        begin
             for i:=2 to trunc(sqrt(n)) do
                   if n mod i=0 then
                      begin
                           kt:=false;
                           break;
                      end;
         end;
end;

begin
   assign(f,'inp.text');
   reset(f);
     readln(f,n);
     for i:=1 to n do read(f,a[i]);
   close(f);
   assign(f,'out.text');
     rewrite(f);
     d:=0;
     for i:=1 to n do
         if kt(a[i])=true then inc(d);
     write(f,d);
   close(f);
end.

đây là bài làm của em anh kiểm tra xem chổ nào chưa hài lòng thì nói em để chính sửa nhé

 

[love_minh95]

cái này không thể chạy đến 10^5 đâu em à.độ phức tạp thuật toán của em có thể là n*căn bậc hai(10^8)=10^5*10^4=10^9.Hơn nữa hàm mod của em chạy khá lâu đó.Xem thuật toán khác nké!!

 

[quanghero100]

cái này không thể chạy đến 10^5 đâu em à.độ phức tạp thuật toán của em có thể là n*căn bậc hai(10^8)=10^5*10^4=10^9.Hơn nữa hàm mod của em chạy khá lâu đó.Xem thuật toán khác nké!!

hjx anh nói thế tức là tính luôn cả số lượt duyệt 10^4 phần tử lun à (L(
giới hạn của anh không quá 10^5 zậy hóa ra việc kiểm tra mổi phần tử chỉ trong 10 lượt thôi sao :-SS:-SS cái này khó à nha nhưng hông sao cứ để em suy nghĩ thêm mới nghĩ ra một thuật toán mới nhưng hông biết có đáp ứng được yêu cầu của anh không nữa @-)@-)

lúc đầu đọc đề của anh em cứ tưởng là mỗi phần tử chỉ dùng tối đa 10^5 lượt duyệt để kiểm tra nguyên tố thôi chứ ai dè thế này ......

 

[quanghero100]

Quang ra đề đi em

bài này anh dùng sàng ơ - cờ - lít

Chắc anh làm sẽ ra

cho anh ý nghĩ chút cũng đc đợi chìu thứ 2 thi xong em sẽ ra đề hì hì

 

[starlove_maknae_kyuhyun]

căng thẳng đó nhỉ ! hì ! cho mình post bài tham khảo được không ! coi như để các bạn sửa lỗi hỳ !
chúc các bạn cạnh tranh tốt nhak ! hì hì )

 

[love_minh95]

optimal

Oài,em có thách đấu thật đâu,nên mới ra đề dễ tkế.hjhj.Mà anh thanh có học chuyên tin khôg?em tửơng anh học a6 mà?mà em có bảo tháck đấu cả 2 đâu sao anh lại gợi ý.hjhj