Phân tích một số ra các thừa số nguyên tố ?

[bld]

thật đơn giản , số dễ dàng nhận thấy các hợp số là bội của các số ngtố và nó chắc chắn phải > số ngtố là ược của nó , vì thế chtrình sẽ vẫn đảm bảo chia số nguyên tố nếu không làm 1 mảng lưu các số nguyên tố và kiểm tra từng số từ nhỏ đến lớn , ta cứ dùng lệnh inc là dược không cần kiểm tra ngtố đâu

tòm lại mình ủng hộ anh f12

[Mr.Bo_Aloha]

Hiện nay theo mình biết thì hàm kiểm tra số nguyên tố tối ưu nhất ( theo nghĩa cấp II) là

Function ngto(a:integer):boolean ;
     var
     begin
              ngto:=false ;
              if a<2 then exit ;
              for i:=2 to trunc(Sqrt(a)) do
                   if a mod i = 0 then exit ;
              ngto:=true ;
   end;

chỉ dáo

[emlaprotheky]

tui chả biết mấy câu lệnh phức tạp như ông Bo nhưng tôi lại thích viết theo kiểu thik gì viết nấy vì vậy theo tôi hàm nguyên tố nên như thế này:

function nt(n:integer):boolean;
var
   i,d:integer;
begin
     d:=1;
     for i:=1 to n do
         if n mod i=0 then
            d:=d+1;
         if d=2 then
            nt:=true
         else
             nt:=false;
end;

chỉ dáo viết sai cố tình hay vô tình vậy

[Mr.Bo_Aloha]

thì viết theo kiểu đó thì nhiều người có thể làm được nhưng tôi đang nói về thuật toán ngắn gọn!!

[=========> Bổ sung bài viết <=========]

chạy từ 1 đến n sẽ tôn thời gian hơn từ 2 ~ truc(sqrt(n)) đó

[bld]

thấy vúi quá !!
mình cũng đóng góp 1 cái :

function nt(a:integer):boolean;
var i:byte;
 begin
  nt:=true
  for i:=1 to round(sqrt(a)) do
   if a mod i=0 then
    begin
     nt:=false;
     break
   end;
  end;

và 1 cái nữa

function nt(a:integer):boolean;
var i:integer;
 begin
 i:=2;
  while a mod i <>0 then
   i:=i+1;
 if i> round(sqrt(a)) then nt:-true 
                      else nt:=false;
 end;

[Mr.Bo_Aloha]

thấy vúi quá !!
mình cũng đóng góp 1 cái :

function nt(a:integer):boolean;
var i:byte;
 begin
  nt:=true
  for i:=1 to round(sqrt(a)) do
   if a mod i=0 then
    begin
     nt:=false;
     break
   end;
  end;

cái này bld chưa xét trường hợp a phải lớn hơn 2 à!
vd: a=-5 khi đó chương trình sẽ báo nt=true!

[thuonghcm]

cái này bld chưa xét trường hợp a phải lớn hơn 2 à!
vd: a=-5 khi đó chương trình sẽ báo nt=true!

Lẽ nào lại báo True, ct sẽ báo lỗi, bằng lằn đỏ.............

[ConanKudo]

Có một thuật toán O(logn^3) nếu mình nhớ ko nhầm,thuật toán Rabbin Miller,còn gọi là thuật toán xấp xỉ với độ sai lệch 1/4^k với k chọn trước

[MMKC_IT]

Ec', anh conan nói thế. Em chịu

[thuonghcm]

"lấy số đó chia cho các số nguyên từ 2 đên sqrt(số đó)" là 1 cách để kiểm tra coi 1 số có phải là số nguyên tố hay không

Còn "lấy số đó chia cho các số nguyên tố từ 2 đên sqrt(số đó)" là 1 cách đúng để phân tích ra thừa số nguyên tố
=> bạn F12 nói không có sai đâu

(chỉ khác nhau có 1 chữ "chia cho các số nguyên tố" và "chia cho các số nguyên" mà thôi)

-thân

éc, hôm nay rảnh lấy ra xem lại ...sao thấy sai béc à!?!?!
em vd:
n:=28; cần pt ra các TSNT;
theo HD trên thì căn(28)=~ 6 (làm tròn)
cho i chạy từ 2 ...6 viết i nếu n chia hết cho i (i là NT)
--> ct sẽ viết 2 2
vậy nên sẽ cho i chạy từ 2...(n div 2) thì cha71c ăn hơn nhỉ