fork download 
  1. def sieve(N):
  2.     n = int(N**0.5)
  3.     prime = [True]*2*(N//6)
  4.     for i in range(6,n+1,6):
  5.         if prime[2*(i//6-1)]:
  6.             k = ((i-1)**2//6)*6
  7.             incr1 = 6*((i-1)-(int((i-1)/3)+1))
  8.             incr2 = 6*(int((i-1)/3)+1)
  9.             for j in range((i-1)**2,N,(i-1)):
  10.                 if j==k-1:
  11.                     prime[2*(j//6)]=False
  12.                     k+=incr1
  13.                 elif j==k+1:
  14.                     prime[2*(j//6)-1]=False
  15.                     k+=incr2
  16.         if prime[2*(i//6-1)+1]:
  17.             k = ((i+1)**2//6)*6
  18.             incr1 = 6*(int(i/3))
  19.             incr2 = 6*((i+1)-int(i/3))
  20.             for j in range((i+1)**2,N,(i+1)):
  21.                 if j==k-1:
  22.                     prime[2*(j//6)]=False
  23.                     k+=incr1
  24.                 elif j==k+1:
  25.                     prime[2*(j//6)-1]=False
  26.                     k+=incr2
  27.     P = [2,3]
  28.     for j in range(len(prime)):
  29.         if prime[j]:
  30.             if j & 1 == 1:
  31.                 P.append(6*(j//2+1)+1)
  32.             else:
  33.                 P.append(6*(j//2+1)-1)     
  34.     return P
Success #stdin #stdout 0.02s 44632KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/DiE7oJ
language:
Python (PyPy 2.7.13)
created:
10 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!