Discussion :

[mmsoaihua]

Bonjour à tous !

J'essaye d'apprendre les algorithmes basiques, malheureusement je me casse la tête et je n’avance pas avec le crible d'Ératosthène.. Il me semble que le premier algorithme écrit dans python as une faute logique.

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
def er_sieve(n):
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
      return sieve, prime_numbers

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Deuxieme: 
// 素数列挙
// nまでの素数をEratosthenesの篩で列挙する
// 計算量O(nloglogn)
template<class T>
vector<T> prime_list(T n){
    vector<T> ret;
    vector<T> isPrime(n+1,1);
    isPrime[0] = isPrime[1] = 0;
    for(long long i = 2; i <= n; ++i){
        if(isPrime[i] == 0) continue;
        ret.push_back(i);
        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;
    }
    return ret;
    // return isPrime;  // 状況によってはこっちを返す
}

Est-ce que les deux algorithmes sont bien écrit? Dans le deuxieme il y a for(j = i*i; j <= j += 1),
mais dans le premièr for j in range(i*2, n+1, i)?!!?!
Merci bien pour votre temps!

[laurent_ott]

Bonjour.
Je ne connais pas Python donc je ne peux pas apporter de réponse à vos questions.
Mais je me permets de vous rappeler le principe du crible d'Ératosthène au cas où ça peut vous aider :
imaginez une grille numérotée de 1 à 100. Partez du nombre 2 et rayez les nombres suivants en avançant de 2 en 2 : c'est-à-dire les nombres 4, 6, 8, 10, 12, etc. Puis partez du nombre 3 et rayez les nombres suivants en avançant de 3 en 3 : les nombres 6, 9, 12, 15, 18, etc. Partez du nombre 4 et rayez les nombres suivants en avançant de 4 en 4 : 8, 12, 16, etc.
En répétant la manipulation jusqu'au nombre 7, vous obtenez cette grille où les nombres qui ne sont pas rayés (ici en orange) donnent la liste des nombres premiers jusqu'à 100 (hormis le 1 qui n'est pas un nombre premier).



Bonne continuation.

[Nebulix]

Cette discussion répond de façon intéressante à la discussion sur les langages d'initiation à l'informatique
(https://www.developpez.net/forums/d2...-informatique/)
Tes exemples de code sont tellement peu lisibles que tu ne t'y retrouves pas toi même.
Il est facile de traduire quasi littéralement en Pascal l'algoritme donné par laurent_ott ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const n=100;
var prime:array[1..n]of boolean;
procedure TForm1.Button1Click(Sender: TObject);//celle qui fait le boulot
var i,j,k,m:integer;
begin
//initialisations
for i:=1 to n do prime[i]:=true;
prime[1]:=false;
m:=trunc(sqrt(n))+1;
//calcul
for i:= 1 to m do if prime[i] then begin
  j:=i;
  while j<=n do begin
    j:=j+i;
    prime[j]:=false;
    end ;
  end;
for i:= 1 to 100 do if prime[i] then memo1.lines.add(inttostr(i));//visu des résultats
end;

[dourouc05]

Tes exemples de code sont tellement peu lisibles que tu ne t'y retrouves pas toi même.

Ah bon ? En quoi ce code Pascal est-il plus lisible ? Il a surtout l'énorme "avantage" de mêler des notions de GUI avec de l'algorithmique… Sans oublier une jolie ligne qui contient une boucle, une condition, puis une instruction. Il ne faut pas confondre incompétence de la personne qui pose une question avec ton incompétence en Python ou en C++ ou avec tes goûts en termes de langage de programmation…

Pour le code Python, j'ai retouché la présentation et remplacé l'utilisation d'entiers par des booléens (vu que ce sont des valeurs binaires et non entières). Ça semble marcher :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def er_sieve(n):
	sieve = [True] * (n+1)
	sieve[0] = False
	sieve[1] = False
 
	for i in range(2, int(n**.5)+1):
		if not sieve[i]: 
			continue
		for j in range(i*2, n+1, i): 
			sieve[j] = False
 
	prime_numbers = [i for i in range(2, n+1) if sieve[i]]
	return prime_numbers

Aurais-tu des cas où tu n'obtiens pas les résultats attendus ?

Pour le code C++, la même modification s'applique : isPrime devrait être un vecteur de booléens (ce qui prendrait au moins soixante-quatre fois moins de mémoire sur une machine 64 bits). Les deux boucles sont bien équivalente, renseigne-toi sur l'utilisation de range() en Python (https://docs.python.org/3.8/library/...es.html#ranges) : partir de 2i (puisqu'on vient de marquer i comme premier, son premier multiple est 2i) ; incrémenter par pas de i (donc passer sur tous les multiples) ; aller jusqu'à la fin des nombres à considérer (n).
La grande différence est en termes d'efficacité (même si ça ne devrait pas changer grand-chose à la complexité asymptotique), c'est que le code Python ne considère des nombres premiers que jusque au lieu de n. Je ne pense pas que ça change grand-chose en termes de correction.

[Pyramidev]

Bonjour,

Voici un code lisible en Python avec les tests unitaires, dont les doctests :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import doctest
from math import sqrt
import sys
import unittest
 
 
def sieve_of_eratosthenes(n):
    """
    Return the prime numbers from 2 to n.
 
    Algorithm: sieve of Eratosthenes
    https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 
    >>> sieve_of_eratosthenes(10)
    [2, 3, 5, 7]
    >>> sieve_of_eratosthenes(11)
    [2, 3, 5, 7, 11]
    """
    assert isinstance(n, int)
    assert n >= 1
    primeness_list = [False, False] + [True] * (n - 1)
    for number in range(2, int(sqrt(n)) + 1):
        the_number_is_prime = primeness_list[number]
        if not the_number_is_prime:
            continue
        for multiple_of_number in range(number*2, n+1, number):
            primeness_list[multiple_of_number] = False
    return [number for number, is_prime in enumerate(primeness_list) if is_prime]
 
 
class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(sieve_of_eratosthenes(1), [])
        self.assertEqual(sieve_of_eratosthenes(2), [2])
        self.assertEqual(
            sieve_of_eratosthenes(100),
            [
                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
                53, 59, 61, 67, 71, 73, 79, 83, 89, 97
            ]
        )
 
if __name__ == "__main__":
    failure_count, _ = doctest.testmod()
    if failure_count != 0:
        sys.exit(1)
    unittest.main()

[Pyramidev]

dourouc05 avait déjà répondu sur la plupart des points importants et j'avais publié mon précédent message un peu trop vite.

Nebulix, j'aimerais bien savoir ce que tu trouves illisible en Python par rapport à du Pascal.

• n**.5 n'est pas joli, mais ce n'est pas la manière idiomatique en Python de calculer une racine carrée. En Python, on peut aussi écrire sqrt(n).
• En Python, quand on connaît le comportement de range, range(number*2, n+1, number) est plus direct que ta boucle while en Pascal. D'ailleurs, on pourrait aussi utiliser while en Python, mais ce serait moins idiomatique dans le cas présent.
• S'il s'agit des déclarations de type, on peut en faire en Python aussi et les vérifier avec un analyseur de typage statique. Par exemple, dans mon code, j'aurais pu aussi annoter la fonction ainsi : def sieve_of_eratosthenes(n: int) -> List[int]:. Cela pourrait être utile dans un plus gros programme pour vérifier le typage dans le code appelant. Mais bon, là, il s'agit d'un simple exercice. Le doctest et les autres tests unitaires illustrent déjà ce que la fonction prend en paramètre et retourne.