fork(27) download
copy 
  1. def sieve(n):
  2.     m = (n-1) // 2
  3.     b = [True]*m
  4.     i,p,ps = 0,3,[2]
  5.     while p*p < n:
  6.         if b[i]:
  7.             ps.append(p)
  8.             j = 2*i*i + 6*i + 3
  9.             while j < m:
  10.                 b[j] = False
  11.                 j = j + 2*i + 3
  12.         i+=1; p+=2
  13.     while i < m:
  14.         if b[i]:
  15.             ps.append(p)
  16.         i+=1; p+=2
  17.     return ps
  18.  
  19. print len(sieve(1000000)) # 78498
Success #stdin #stdout 0.61s 6732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
78498
https://ideone.com/YTaMB
language:
Python (cpython 2.7.16)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!