## 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 1,949

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.

@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 1,391

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 1,391

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.