Решето Эратосфена на Python.

sieve_of_eratosthenes.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

n = input("Вывод простых чисел до числа (включительно): ") + 1

# Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
a = [True] * n

# Берëм невычеркнутые числа от 2 до sqrt(n)
for i in xrange(2, int(math.sqrt(n))):
	# Вычëркиваем числа, кратные невычеркнутому
	for j in xrange(i * 2, n, i):
		a[j] = False

# Все невычеркнутые числа - простые
b = [i for i in xrange(2, n) if a[i]]

print(b)

не работает до 8 включительно