Sieve of Erastothenes simply with nested loops

[kouty]

Have a good evening!

The Aim: to obtain a Sieve of Erastothenes

The Means: to build a function of a number n that the prime numbers up to n.

The code supposed to make this

from math import sqrt
def holeofStrainer():
  """The purpose is to build a sieve of Erasthotenes. 
  We beginn with a sieve without holes, called biglist. 
  The indexes of the list have a double function: 
  First, The natural list indexation. II-st, there are 
  as keys of the corresponding list items(the boolean 
    values of the prime being question about each number). 
We have for each index a"""
  bigList = [False, False] + [True]*100
  print("line 11 - bigList : ", bigList)
  for num in range(3, 101):
    print("line 13 - num : ", num)
    # I f we don't find divisors of nume littler that sqrt(num)
    # it is guaranted that num is prime.
    # 'int(sqrt(num)) + 1' is the first integer greater than sqrt(num)
    for x in range(bigList[2], bigList[int(sqrt(num)) + 1]):
      print("line 18 x  is equal to %d"%x)
      if num % x == 0:
        print("line 20 {0} divided by {1} = {2} ".format(num, x, num/x))
        bigList[num] == False
        print ("bigList index {0} == {1}".format(num, bigList[num]))
      bigList[num] == True

    for multiple in range (2, int(101/num) + 1):
      bigList[multiple] = False
  return(bigList) #We expect a 'sieve with many holes'
print("the last result of bigList {} ".format(holeofStrainer()))

The wished unrolling of the code

line 11 biglist [False, False, True …...True]
line 13 num 3
line 18 x :2
line 20: 3 divided by 2 is equal to 1.5
biglist index 3 == True
line 13 num 4
line 18 x:2
line 20 4 divided by 2 is equal to 2
biglist index 4 == False

The disapointing output:

line 11 - bigList :  [False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
the last result of bigList [False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True] 

The request.
Where is the obvious lack of understanding in the loop principle?
If that is a tutorial that reffers directly to this kind of error, it is welcome.

[kouty]

@tinstaafl
How may we delete or update a question?

[kouty]

@tinstaafl
- FIRST
I make an effort to clarify and modify a question
in many websites it is easy, a tab withe a little pencil permitt to re-edit an old question.
But here it was not possible. -> i make a new question.
the new question was submitted but the website buuged, I try again and the both trials were publicated

• II
  But clearly:
  I ask without renoouncement! I need to know!!! I need to understand!!!!
  -III
  Have a nice day!!!!!

[pritaeas]

How may we delete or update a question?

Delete: you cannot. You may request it from a moderator, but it is unlikely your request will be honoured.

Update: You have 30 minutes to edit your question, after that it is locked. Additions after that time will have to be in a reply to your own post.

[kouty]

@pritaes
OK. Now I know.
good smocking

[kouty]

I try to reply to myself but it's not the final response

from math import sqrt
def holeofStrainer():
  """The purpose is to build a sieve of Erasthotenes. 
  We beginn with a sieve without holes, called biglist. 
  The indexes of the list have a double function: 
  First, The natural list indexation. II-st, there are 
  as keys of the corresponding list items(the boolean 
    values of the prime being question about each number). 
We have for each index a"""
#first we initialize the list of the boolean value of the 
# primality of each index of the list.
  bigList = [False, False] + [True]*100
  print("line 13 - bigList : ", bigList)
  # now we test each number, equivalent to a index of biglist, if 
  # he is prime.
  for num in range(3, 101):
    print("line 17 - num : ", num)
    # I f we don't find divisors of nume littler that sqrt(num)
    # it is guaranted that num is prime.
    # 'int(sqrt(num)) + 1' is the first integer greater than sqrt(num)
    if bigList[num] == False:
      continue
    else:
      for x in range(2, int(sqrt(num)) + 1):
        # x is an integer
        print("line 26 x  is equal to {0} for an num equal to {1}".format(x, num))
        if num % x == 0:
          print("line 28 {0} divided by {1} = {2} ".format(num, x, num/x))
          bigList[num] = False
          print ("bigList index {0} == {1}".format(num, bigList[num]))
          break
        else:
          pass

        bigList[num] = True
        print (" line 36 bigList index {0} == {1}".format(num, bigList[num]))
        for multiple in range (2, int(101/num) + 2):
          bigList[multiple * num] = False
  return(bigList) #We expect a 'sieve with many holes'
print("the last result of bigList {} ".format(holeofStrainer()))

[kouty]

This is good?

from math import sqrt
def holeofStrainer():
  """The purpose is to build a sieve of Erasthotenes. 
  We beginn with a sieve without holes, called biglist. 
  The indexes of the list have a double function: 
  First, The natural list indexation. II-st, there are 
  as keys of the corresponding list items(the boolean 
    values of the prime being question about each number). 
We have for each index a"""
#first we initialize the list of the boolean value of the 
# primality of each index of the list.
  bigList = [False, False] + [True]*100
  print("line 13 - bigList : ", bigList)
  # now we test each number, equivalent to a index of biglist, if 
  # he is prime.
  for num in range(3, 101):
    print("line 17 the num is ", num)
    # I f we don't find divisors of nume littler that sqrt(num)
    # it is guaranted that num is prime.
    # 'int(sqrt(num)) + 1' is the first integer greater than sqrt(num)
    if bigList[num] == False:
      print("The num {0} is already know as not prime".format(num))
      continue
    else:
      for x in range(2, int(sqrt(num)) + 1):
        # x is an integer
        print("line 26 x  is equal to {0} is it a divisor of num {1}?".format(x, num))
        if num % x == 0:
          print("line 28 {0} divided by {1} = {2} ".format(num, x, num/x))
          bigList[num] = False
          print ("line 30 bigList index {0} == {1}".format(num, bigList[num]))
          break
        else:
          print("line 33 x is equal to {0} and is not divisor of num {1}".format(x, num))
          pass

          bigList[num] = True
      print (" line 37 bigList index {0} == {1}".format(num, bigList[num]))
      for item in range (2, int(101/num) + 2):
        ple = item * num
        if ple < len(bigList):
          bigList[ple] = False
  return(bigList)
  print("the last result of bigList is {0} ".format(bigList)) #We expect a 'sieve with many holes'
holeofStrainer()
print("the last result of bigList {} ".format(holeofStrainer()))

[kouty]

Finally something valid. More, the orthography is Eratosthene. It was a Freudian condensation with Aristophane.
The code actualy for me is:

def kevara(n):
    marked = [False, False] + [True] * (n - 1)
    for p in range(2, n + 1):
        for i in range(p, int(n / p) + 1):
            marked[p*i] = False
    return marked
isPrime = kevara(1000000)
print(isPrime)

If someone know how to improve it without supplementary tools, I am Buyer. The mecanism of the sieve is that the first not-not prime number that appairs after testing the multiples of the precedent numbers is necessary a realy prime number. the first multiple of this number we need to search is his square, because before this, the multiples are already checked ad multiples of the precedent numbers!

[Gribouillis]

A possibility is to use an array.array instead of a list. It is a little slower but it takes about 8 times less memory.

#!/usr/bin/env python3
# -*-coding: utf8-*-
'''Compares Sieves of Eratosthenes with list or array implementation
'''

from array import array

### Vegaseat code to time the function ###
# https://www.daniweb.com/software-development/python/code/486298/a-timing-decorator-python
import time
from functools import wraps
from sys import getsizeof

def print_timing(func):
    '''
    create a timing decorator function
    use
    @print_timing
    just above the function you want to time
    '''
    @wraps(func)  # improves debugging
    def wrapper(*arg):
        start = time.perf_counter()  # needs python3.3 or higher
        result = func(*arg)
        end = time.perf_counter()
        fs = '{} took {:.3f} microseconds'
        print(fs.format(func.__name__, (end - start)*1000000))
        return result
    return wrapper
### end of timing code ###

@print_timing
def kevara(n):
    marked = [False, False] + [True] * (n - 1)
    for p in range(2, n + 1):
        for i in range(p, int(n / p) + 1):
            marked[p*i] = False
    return marked

@print_timing
def kevara2(n):
    marked = array('B', [1]) * (n+1)
    marked[0], marked[1] = 0, 0
    for p in range(2, n + 1):
        for i in range(p, int(n / p) + 1):
            marked[p*i] = 0
    return marked

if __name__ == '__main__':
    N = 1000000
    result = kevara(N)
    result2 = kevara2(N)
    assert result == [bool(item) for item in result2]
    print('{}\n{}'.format(getsizeof(result), getsizeof(result2)))

"""my output -->

kevara took 1545919.702 microseconds
kevara2 took 1694313.921 microseconds
8000072
1000065
"""

[kouty]

@gribouilli
The amount of knowledge you demonstrate in this script is very outside my competence.
Did you want to show me a little tutorial?

[Gribouillis]

Well, it is not very important to understand the section between ###...### (the definition of the print_timing() function). You can understand it later on, when you will study python's decorators. It is sufficient to know that if you write @print_timing before a function definition, it will print the time it takes to run every time the function is called.

kevara() is your own function, I suppose you understand it. kevara2() is the same function written using an array of small integers instead of a list.

An array is a data structure similar to a list in many ways. For example, this code creates an array of 10 small unsigned integers:

>>> from array import array
>>> array('B', [1]) * 10
array('B', [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

In kevara2(), the array is filled with values 0 or 1 to indicate False or True. The 'B' in the array creation tells python that the array items are small integers. A small integer takes 1 byte of memory (8 bits), while a python integer takes 28 bytes on my 64 bits computer. The use of getsizeof() is an attempt to compute the memory size of the objects in bytes, although it is better to use Raymond Hettinger's total_size() method.

A shorter memory footprint could be achieved by using a bitarray structure from module bitarray (1 bit per boolean value), but it turns out to be slower.

[kouty]

@gribouillis
Thanks a lot. Interesting, in Ruby language the lists are called array.