Code sàng số nguyên tố c++ và pascal

Tham khảo code sàng nguyên tố:

Code sàng nguyên tố pascal

const
        nmax=1000;
var
        SNT:array[0..nmax+1] of boolean;

procedure sangnt;
var     i,j:longint;
begin
        fillchar(snt,sizeof(snt),true);
        snt[1]:=false;
        i:=2;
        while i<=trunc(sqrt(nmax)) do
                begin
                        while snt[i]=false do
                                inc(i);
                        for j:=2 to nmax div i do
                                snt[i*j]:=false;
                        inc(i);
                end;

        for i:=1 to nmax do
                if snt[i]=true then
                        write(i,' ');
end;

begin
        sangnt;
        readln;
end.

 

Code sàng nguyên tố c++

#include <iostream>
#include <math.h>
using namespace std;
const int MAXSANG = 1000;

int snt[MAXSANG+1];

void sangnt()
{
    long i,j;
    for (i=1; i<=MAXSANG; i++)
        snt[i]=1;
    snt[1]=0;
    i=2;
    while (i<=sqrt(MAXSANG))
    {
        while (snt[i]==0)
            i++;
        for (j=2; j<=MAXSANG/i; j++)
            snt[i*j]=0;
        i++;
    }
}

int main()
{
    sangnt();
	for (int i=1; i<=1000; i++)
		if (snt[i]) cout<< i<<endl;
    return 0;
}

 

Độ phức tạp thuật toán O(n)

2 thoughts on “Code sàng số nguyên tố c++ và pascal

  1. Có thể giải thích cho em được không ạ? Em là học sinh cấp 2 nên chưa biết nhiều. Mong ad giải thích cho em. Xin cảm ơn!

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *