若i为素数，则设置a[i]为1；反之则设置为0.

首先，将所有数组的元素设置为1，表示没有已知的非素数。然后将已知为非素数（即为已知素数的倍数）的索引对应的数组元素设置为0。如果将所有较小的素数的倍数都设置为0之后，a[i]仍然保持为1，则可判断它是所找的素数。

 #include<stdio.h>

#define

 N 10000

int

 main()

{ 

int

 i, j, a[N];

    

for

 (i 

=

 

2

; i 

<

 N; i

++

) a[i] 

=

 

1

;

    

for

 (i 

=

 

2

; i 

<

 N; i

++

)

      

if

 (a[i])

        

for

 (j 

=

 i; j 

<

 N

/

i; j

++

) a[i

*

j] 

=

 

0

;

    

for

 (i 

=

 

2

; i 

<

 N; i

++

)

      

if

 (a[i]) printf(

"

%4d 

"

, i);

    printf(

"

\n

"

);

    

return

 

0

;

}

  因为程序使用一个数组来包含最简单元素类型，0和1两个值，如果我们使用位的数组，则可以获得更高的空间有效性。

而且，如果N庞大，一些编程环境可能要求数组为全局，或是可以动态分配它。

 #include <stdlib.h>

main(

int

 argc, 

char

 

*

argv[])

  { 

long

 

int

 i, j, N 

=

 atoi(argv[

1

]);

    

int

 

*

a 

=

 malloc(N

*

sizeof

(

int

));

    

if

 (a 

==

 NULL) 

      { printf(

"

Insufficient memory.\n

"

); 

return

; }

    ...