Skip to content
Snippets Groups Projects
Select Git revision
  • d37ca5c2b30f69146f4a82ee040c55e9181eec4f
  • main default protected
2 results

eratosthenes.py

  • user avatar
    Jocelyne authored
    d37ca5c2
    History
    Code owners
    Assign users and groups as approvers for specific file changes. Learn more.
    eratosthenes.py 1.15 KiB
    #!/usr/bin/env python3
    import math, sys
    
    def usage_exit(exit_code):
      sys.stderr.write('Usage: {} <integer >= 3>\n'
                        .format(sys.argv[0]))
      exit(exit_code)
    
    if len(sys.argv) != 2:
      usage_exit(1)
    
    try:
       n = int(sys.argv[1])
    except:
       usage_exit(2)
    
    if n <= 2:
       usage_exit(3)
    
    '''
    Implement the Algorithm 'Sieve of Eratosthenes' after the line
    initializing the list marked below, as described in the exercise sheet.
    After the marking process has finished, create a list
    primes of all i, 2<=i<=n, such that marked[i] is not True.
    This is the list of prime numbers, which is output in the code below
    '''
    marked = [None,None] + ([False] * (n-1))
    
    x = 2
    while x**2 <= n:
      for i in range(x+1,n+1):
        if i % x == 0:
          marked[i] = True
      x += 1
      while marked[x] == True:
        x += 1
    
    primes = []
    for i in range(2,n+1):
      if not marked[i]:
        primes.append(i)
    
    num_primes = len(primes)
    print('there are {} prime numbers <= {}'.format(num_primes,n))
    show_primes = 10
    print('the largest {} prime numbers <= {} are:'
          .format(min(num_primes,show_primes),n))
    for i in range(max(0,num_primes-show_primes),num_primes):
      print('{}'.format(primes[i]))