fork download
copy 
  1. def sieve(N):
  2.     n = int(N**0.5)
  3.     p = list(range(n+1))
  4.     for j in range(2,n+1):
  5.         if p[j]:
  6.             for k in range(j**2,n+1,j):
  7.                     p[k]=False
  8.     P = [l for l in p[2:] if l]
  9.     m = 1
  10.     while (m+1)*n < N:
  11.         u = (m+1)*n+1
  12.         p = list(range(m*n+1,u))
  13.         for x in P:
  14.             v = x*((m*n)//x+1)
  15.             if v > u:
  16.                 break
  17.             for y in range(v,u,x):
  18.                 p[y-m*n-1]=False
  19.         for j in range(len(p)):
  20.             if p[j]:
  21.                 if p[j] > n**0.5+m*n+1:
  22.                     break
  23.                 for k in range(p[j]**2,p[-1]+1,p[j]):
  24.                     p[k]=False
  25.         P+=[l for l in p if l]
  26.         m+=1
  27.     p = list(range(m*n+1,N+1))
  28.     for x in P:
  29.         v = x*((m*n)//x+1)
  30.         if v > N and v/(x)*(x-1) > m*n+1:
  31.             v = v//x*(x-1)
  32.         for y in range(v,N+1,x):
  33.             p[y-m*n-1]=False
  34.     for j in range(len(p)): 
  35.             if p[j]:
  36.                 if p[j] > n**0.5+m*n+1:
  37.                     break
  38.                 for k in range(p[j]**2,p[-1]+1,p[j]):
  39.                     p[k]=False
  40.     P+=[l for l in p if l]
  41.     return P
Success #stdin #stdout 0.02s 44632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bj7XXV
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!