fork download
copy 
  1. import sys
  2. import math
  3.  
  4. if sys.version_info < (3,):
  5.     range = xrange
  6.  
  7. def primes(upto, func):
  8.     if upto > 25000: return large_primes(upto, func)
  9.     upto -= 1
  10.     flags = [True] * upto
  11.     for i in range(upto-1):
  12.         if flags[i]:
  13.             prime = i + 2
  14.             k = i + prime
  15.             while k < upto:
  16.                 flags[k] = False
  17.                 k += prime
  18.             func(prime)
  19.  
  20. def large_primes(upto, func):
  21.     # The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
  22.     # This code is a translated version of Andreas Raab's #largePrimesUpTo:do: method
  23.     # which was written for the Squeak Smalltalk environment.
  24.  
  25.     idx_limit = math.sqrt(upto) + 1
  26.     flags = [0xFF] * (int((upto + 2309) / 2310) * 60 + 60)
  27.     primes_up_to_2310 = []
  28.     primes(2310, lambda p: primes_up_to_2310.append(p))
  29.     mask_bit_idx = [None]*2310
  30.     mask_bit_idx[0] = 0
  31.     mask_bit_idx[1] = 1
  32.     bit_idx = 1
  33.     for i in range(5):
  34.         func(primes_up_to_2310[i])
  35.     idx = 5
  36.     for n in range(2, 2310):
  37.         while primes_up_to_2310[idx] < n: idx += 1
  38.         if n == primes_up_to_2310[idx]:
  39.             bit_idx += 1
  40.             mask_bit_idx[n] = bit_idx
  41.         elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
  42.             mask_bit_idx[n] = 0
  43.         else:
  44.             bit_idx += 1
  45.             mask_bit_idx[n] = bit_idx
  46.     for n in range(13, upto, 2):
  47.         mask_bit = mask_bit_idx[n % 2310]
  48.         if mask_bit:
  49.             byte_idx = int(n / 2310) * 60 + (mask_bit-1 >> 3)
  50.             bit_idx = 1 << (mask_bit & 7)
  51.             if flags[byte_idx] & bit_idx:
  52.                 func(n)
  53.                 if n < idx_limit:
  54.                     idx = n * n
  55.                     if (idx & 1) == 0: idx += n
  56.                     while idx <= upto:
  57.                         mask_bit = mask_bit_idx[idx % 2310]
  58.                         if mask_bit:
  59.                             byte_idx = int(idx / 2310) * 60 + (mask_bit-1 >> 3)
  60.                             mask_bit = 255 - (1 << (mask_bit & 7))
  61.                             flags[byte_idx] = flags[byte_idx] & mask_bit
  62.                         idx += 2 * n
  63.  
  64. max = int(sys.argv[1]) if len(sys.argv) == 2 else 100
  65. q = c = 0
  66.  
  67. def f(p):
  68.     global q, c
  69.     q = p
  70.     c += 1
  71.  
  72. primes(max, f)
  73. print(q, c)
  74.  
Success #stdin #stdout 0.08s 10840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(97, 25)
https://ideone.com/KNOE0
language:
Python (cpython 2.7.16)
created:
12 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!