Sieve of Eratosthenes

Decimos que un número es primo si solo es divisible por 1 y por sí mismo. 2, 3 y 5 son ejemplos de números primos. En otro caso, se llama compuesto.

Para saber si un número n es primo, podríamos recorrer un ciclo desde 2 hasta n-1 y verificar si alguno lo divide. Si algún número lo divide, entonces no es primo.

¿Es primo? O(n)

bool esPrimo(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; }

Si tomamos un número n y buscamos sus divisores, estos aparecen en pares. Por ejemplo, si 4 es divisor de 28, entonces también lo es 28 / 4 = 7. Así, obtenemos el par (4, 7).

Esto significa que para todo divisor d de n, existe un divisor correspondiente n/d. Si d es menor o igual que √n, entonces n/d será mayor o igual que √n.

Por lo tanto, solo es necesario verificar divisores hasta la raíz cuadrada de n. Si n tiene un divisor mayor a su raíz cuadrada, su divisor correspondiente será menor y ya lo habríamos revisado.

¿Es primo? O(√n)

bool esPrimo(int n) { for (int i = 2; i*i < n; i++) { if (n % i == 0) { return false; } } return true; }

0

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

90

91

92

93

94

95

96

97

98

99

100

vector<bool> criba(int n) { vector<bool> prime(n+1, true); prime[0] = prime[1] = false; for (int i = 2; i <= n; i++) { if (prime[i]) { for(int j = 2*i; j <= n; j += i) { prime[j] = false; } } } return prime; }

O(n log log n)

vector<bool> criba(int n) { vector<bool> prime(n+1, true); prime[0] = prime[1] = false; for (int i = 2; i*i <= n; i++) { if (prime[i]) { for(int j = i*i; j <= n; j += i) { prime[j] = false; } } } return prime; }