100000        1000000
Haskell          1.82 sec       47.7 sec
C GCC 3.4.5      0.44 sec       11.3 sec
ComponentPascal  0.65 sec       17.0 sec

primes'wheel :: [Int]
primes'wheel = 2:3:5:7:filter isPrime'wheel (spin wheel2357 11)
  where
    isPrime'wheel :: Int -> Bool
    isPrime'wheel !x = all (\p -> x `mod` p /= 0) $ takeWhile (\p -> p*p <= x) $ tail primes'wheel

    wheel2357 :: [Int]
    wheel2357 = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
                4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel2357

    spin :: [Int] -> Int -> [Int]
    spin (x:xs) n = n:spin xs (n + x)

#define maxn 1000000

int ps[maxn];

int primes_c (int n)
{
    int  i = 2, j, p = 5, f;
    ps[0] = 2; ps[1] = 3;
    while (i < n)
    {
        f = 1; j = 1;
        while (f && (ps[j]*ps[j] <= p))
        {
            f = (p % ps[j]);
            j++;
        }
        if (f)
        {
            ps[i] = p;
            i++;
        }
        p += 2;
    }
    return ps[i-1];
}

MODULE Primes;
IMPORT SL:=StdLog;

CONST nmax = 1000000;
VAR ps : ARRAY nmax OF INTEGER;

PROCEDURE Prime(n : INTEGER) : INTEGER;
VAR i, j, p : INTEGER;
    f : BOOLEAN;
BEGIN
  ps[0] := 2; ps[1] := 3;
  i := 2; p := 5;
  WHILE i < n DO
    f := TRUE;
    j := 1;
    WHILE f & (ps[j]*ps[j] <= p) DO
      f := (p MOD ps[j]) # 0;
      INC(j)
    END;
    IF f THEN
      ps[i] := p;
      INC(i)
    END;
    INC(p,2)
  END;
  RETURN ps[n-1]
END Prime;

PROCEDURE Do*;
BEGIN
  SL.Int(Prime(1000000)); SL.Ln;
END Do;

END Primes.

{-# OPTIONS -O2 -optc-O -fbang-patterns #-}
--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- Contributed by Don Stewart
-- nsieve over an ST monad Bool array
--

import Control.Monad.ST
import Data.Array.ST
import Data.Array.Base
import System
import Control.Monad
import Data.Bits
import Text.Printf

main = do
    n <- getArgs >>= readIO . head :: IO Int
    mapM_ (sieve . (10000 *) . (2 ^)) [n, n-1, n-2]

sieve n = do
   let r = runST (do a <- newArray (2,n) True :: ST s (STUArray s Int Bool)
                     go a n 2 0)
   printf "Primes up to %8d %8d\n" (n::Int) (r::Int) :: IO ()

go !a !m !n !c
    | n == m    = return c
    | otherwise = do
          e <- unsafeRead a n
          if e then let loop !j
                          | j < m     = do
                              x <- unsafeRead a j
                              when x $ unsafeWrite a j False
                              loop (j+n)

                          | otherwise = go a m (n+1) (c+1)
                    in loop (n `shiftL` 1)
               else go a m (n+1) c

#include <iostream>
#include <vector>

int main () {
    int n = 0;
    std::cin >> n;
    std::vector<bool> prime (n);
    for (int i=2; i<n; ++i) prime[i]=true;
    for (int i=2; (i*i)<=n; ++i) {
        if (prime[i])
            for (int j=(i*i); j<=n; j+=i)
                prime[j]=false;
    }

    for (int i=0; i<n; ++i) if (prime[i]) std::cout << " " << i;
    std::cout << std::endl;
    return 0;
}

    f := TRUE;
    j := 1;
    WHILE f & (ps[j]*ps[j] <= p) DO
      f := (p MOD ps[j]) # 0;
      INC(j)
    END;
    IF f THEN
      ps[i] := p;
      INC(i)
    END;

prime' n = loop1 (listArray (2,n) (repeat True)) 2 n
           where
               loop1 arr i n | (i*i)>n  = arr
               loop1 arr i n | (arr ! i)= loop1 (loop2 arr (i*i) i n) (i+1) n
               loop1 arr i n            = loop1 arr (i+1) n
               loop2 arr j i n | j<=n = loop2 (arr//[(j,False)]) (j+i) i n
               loop2 arr j i n        = arr

main = do  s <- getLine
           cout (prime' $ read s) 2 (read s)

cout :: Array Int Bool -> Int -> Int -> IO ()
cout arr i n | i<=n && (arr ! i) = do print i
                                      cout arr (i+1) n
cout arr i n | i<=n = cout arr (i+1) n
cout arr i n        = print "--"