PDA

Xem phiên bản đầy đủ : Bài tập Pascal về số nguyên tố


shsh
02-02-2010, 21:37
Ai có ý tưởng hay về bài toán này thì giúp em với nha.Cảm ơn mọi ngươi trước nhé.
Bài toán như sau: Nhập vào số nguyên n(n<=100) viết chương trình in ra n số nguyên tố đầu tiên.

chibi
02-02-2010, 22:33
Chắc là in ra n số nguyên tố đầu tiên?

shsh
02-02-2010, 22:37
hihi em gõ nhầm chút. bài toán là in ra n số nguyên tố đầu tiên.

shsh
02-02-2010, 22:40
program tinh_tong;
uses crt;
var i,n:integer; s:longint;
begin
clrscr;
write('nhap so nguyen n=');readln(n);
s:=0;
for i:=1 to n do s:=s+i;
writeln('tong ',n,' so tu nhien dau tien la: ',S);
readln
end.
Cảm ơn bác nhưng nếu bài toán đó thì đã quá đơn giản rồi. Em gõ nhầm chút yêu cầu của bài toán là đưa ra n số nguyên tố đầu tiên. tức là ví dụ nhập n=5 thi phai đưa ra màn hình là:2 3 5 7 11

ptmn1984
02-02-2010, 23:18
Xin lỗi! Mình lạc đề rồi. Hẹn hôm khác nhé! Buồn ngủ quá!

Nhất Điểm Tuyết
02-02-2010, 23:28
lần trước thảo luận về sàng Erathostene Tuyết có thử viết 1 đoạn code , cô thử tham khảo nhé:


int N = 100;
int[] A = new int[100]; //array to store prime numbers

A[0] = 2;
A[1] = 3;
int k = 1; //only consider those numbers of the form 6k-1 and 6k+1
int sizeOfA = 2; //current size of A
int index;

while (sizeOfA < N)
{
for (int num = 6 * k - 1; num <= 6 * k + 1; num += 2)
{
index = 1;
while ((A[index] <= Math.Sqrt(num)) && (num % A[index] != 0))
{
index++;
}
if (A[index] > Math.Sqrt(num)) //num is a prime
{
A[sizeOfA] = num;
sizeOfA++;
}
}
k++;
}

//print out the array of prime numbers

for (int i = 0; i < sizeOfA; i++)
{
Console.Write(A[i] + "\t" );
}
Console.ReadKey();

ttk41
03-02-2010, 13:01
lần trước thảo luận về sàng Erathostene Tuyết có thử viết 1 đoạn code , cô thử tham khảo nhé:


int N = 100;
int[] A = new int[100]; //array to store prime numbers

A[0] = 2;
A[1] = 3;
int k = 1; //only consider those numbers of the form 6k-1 and 6k+1
int sizeOfA = 2; //current size of A
int index;

while (sizeOfA < N)
{
for (int num = 6 * k - 1; num <= 6 * k + 1; num += 2)
{
index = 1;
while ((A[index] <= Math.Sqrt(num)) && (num % A[index] != 0))
{
index++;
}
if (A[index] > Math.Sqrt(num)) //num is a prime
{
A[sizeOfA] = num;
sizeOfA++;
}
}
k++;
}

//print out the array of prime numbers

for (int i = 0; i < sizeOfA; i++)
{
Console.Write(A[i] + "\t" );
}
Console.ReadKey();

Đây là cải tiến của phương pháp duyệt mọi ước đê kiểm tra tính nguyên tố mà, còn tư tưởng sàng Erathostene là loại bỏ mọi bội của các số nguyên tố ra khỏi tập số cần xét :D
Cách làm khác: lập 1 mảng A 1 chiều kích thước n/2 lưu các số nguyên tố từ 1 đến n/2, khi cần kiểm tra 1 số x có phải là số nguyên tố ko thì ko duyệt các ước 2->sqrt(x) mà chỉ cần duyệt các số nguyên tố 2->sqrt(x) lưu trong A
VD x= 27 =>sqrt(x) =5, ta ko cần kt x chia hết 2,3,4,5 mà chỉ cần kt x có chia hết 2,3,5 (số nguyên tố lưu trong A )ko thôi, nếu x là nguyên tố thì thêm vào A. Lưu ý sau này khi số cần kt phạm vi tăng nhanh nhưng số nguyên tố tăng ít (~ n/lg(n) ,sachs nó nói thế :D) nên thuật toán nhanh hơn rất nhiều
Góp ý thêm cho tuyết là cố gắng dùng pascal cho các thày cô dễ hiểu hơn nhé, với lại code C quen sau này giảng dạy quay lại Pascal thấy cực lắm( cũng đang cố ko bị phong cách lập trình C ảnh hưởng sang Pascal :D )

Nhất Điểm Tuyết
03-02-2010, 13:52
Đoạn code trên của Tuyết chính là cái cách làm khác muh thầy đề cập.

|************************************************|
while ((A[index] <= Math.Sqrt(num)) && (num % A[index] != 0))
|************************************************|

chỉ xét các số nguyên tố từ 3 đến sqrt(num) vì A[] chỉ chứa các số nguyên tố.

Vì không có Pascal để test nên thường em chỉ nêu ý tưởng, lần này có sẵn code nên copy paste ra thôi, nếu thầy có thể chuyển nó sang Pascal thì tốt quá, các thầy cô sẽ dễ hiểu hơn

ttk41
03-02-2010, 14:02
Chết Sorry Tuyết chưa đọc kĩ rồi, tại tập trung đoạn
for (int num = 6 * k - 1; num <= 6 * k + 1; num += 2)quá nên hố :D,
Tuyết có rảnh qua topic thày linhthaodn, rất muốn nghe ý kiến của Tuyết về mấy bài trong đó :D

phuongqt
14-03-2010, 23:21
Không biết cái này có phù hợp với ý của bạn ShSh không?

var i,j,n,d:byte;
ok:boolean;
begin
write('Nhap N= ');
readln(n);
if n=1 then write(2);
if n=2 then write(2,' ',3)
else
begin
i:=4; d:=2;
while d<n do
begin
ok:=true;
for j:=2 to i-1 do
if i mod j =0 then
Begin
ok:=false;
Break;
End;
if ok then
begin
write(i:3);
d:=d+1;
end;
i:=i+1;
end;
end;
readln
end.

shsh
15-03-2010, 20:04
Cảm ơn bác Phuongqt nha, t đọc qua chương trình cũng thấy rất dễ hiểu, cái này dễ hiểu hơn phương pháp sàng nhiều. cảm ơn bác nha.

phuongqt
15-03-2010, 23:02
Vâng! Không có chi. Miễn là giúp ích được cho ShSh và mọi người là Phuongqt thấy vui vui rồi...