The Sieve of Eratosthenes has been recently extended by excluding, for a givenkthe multiples of the firstkprimes from the initial set. The approach developed lends itself nicely to massive parallelism. Four data layouts are presented for a massively parallel SIMD architecture. It is shown that the mapping of data directly affects the performance of the algorithm. Communication strategies are examined to see the impact on the performance of the algorithm.