02/10/2018, 13:58
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | 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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #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)
