Gentlemen, here's a simple challenge

I'm testing something to kill time. Can I ask for an efficient Perl, Java, C and C++ implementations of the following Python? (Also, if you have any ideas on how to make this more efficient in Python, you're welcome to own me.)

The first function calculates primes up to max using a classic algorithm. Do not change the algorithm, just try to make the code as fast as possible; tricks allowed as long as you stick to this algorithm.

The second function implements a Sieve of Eratosthenes using dictionaries (hashes), which takes an assload of memory but is much faster. Again, don't change the algorithm, but you can use any data structure you see fit.

tl;dr version: Could you port the following into efficient Perl, Java, C and C++? No need to understand what they do.

def Primes(max):
    a = []
    for i in xrange(1, max + 1):
        prime = True
        for j in xrange(2, int(sqrt(i)) + 1):
            if not i % j:
                prime = False
                break
        if prime:
            a += [i]
    return a

def Erat(size):
    size1 = size + 1
    s = dict.fromkeys(xrange(2, size1), None)
    for n in xrange(2, int(sqrt(size)) + 1):
        if n in s:
            for i in xrange(n << 1, size1, n):
                if i in s:
                    del s[i]
    return [1] + list(s)

except that 1 is not prime.
Oops. Turns out it is not. (The definition, as I just checked it, said numbers that have two distinct divisors, while I worked with the definition of numbers that can only be divided by 1 and themselves, which basically had allowed 1.)

and if you add [1] to the beginning of the array, that shifts the other values so that s[3] represents 2, s[4] represents 3, etc.
list(s) is [2, 3, 5, 7, 11, 13...], adding 1 it was [1, 2, 3, 5, 7, 11, 13...]; either way s[x] is not meant to be x.