Exercice corrigé Ancien programme

algorithme du crible d'ératostène

1. a. Construire un tableau de 10 lignes et 10 colonnes contenant tous les entiers compris entre 1 et 100 (la 1re ligne contiendra tous les entiers entre 1 et 10).

b. Barrer 1 (car il n'est pas premier) et entourer 2. Barrer tous les multiples suivants de 2. Le premier entier non barré supérieur à 2 (ici 3) est premier. Pourquoi ?

On entoure ainsi 3 et on barre tous les multiples de 3, . . .

c. On a ainsi entouré 2, 3, 5, . . . , p.

Soit q le premier entier non barré supérieur à p. Est-il premier ? Quel est le premier multiple de q qui n'a pas été encore barré ?

En déduire le moment où le processus s'arrête.

d. Déterminer tous les nombres premiers compris entre 2 et 100.

2. Déterminer de même tous les nombres premiers compris entre 2 et 400 à l'aide d'un tableau de 20 lignes et 20 colonnes.

1. a.

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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

89

91

92

93

94

95

96

97

98

99

100

b. Un entier supérieur ou égal à 2 est premier s'il n'est divisible par aucun

nombre premier strictement plus petit que lui. 3 n'est pas barré, car il n'est pas

divisible par 2, le seul nombre premier strictement plus petit que lui.

Donc 3 est premier.

c. q est le premier entier non barré supérieur à p : il n'est pas un multiple de 2,

3, ..., p qui sont les seuls nombres premiers inférieurs à q, donc q est premier.

Les multiples de q qui ont été déjà barrés sont 2q, 3q, ..., pq (car ce sont des

multiples de 2, ..., p) et (caront été barrés car ils étaient des multiples de 2, ..., p).

Donc le premier multiple de q qui n'est pas encore barré est q2 : le processus

s'arrête donc quand .

d. D'après la question précédente, le processus s'arrête lorsque q = 11 et tous les entiers non barrés sont premiers. Les nombres premiers compris entre 2 et 100 sont donc 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.

2. Le processus s'arrête lorsque q = 23. Les nombres premiers compris entre 2 et 400 sont 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner