Um número é primo se tem como divisor o número 1 e ele mesmo. Apesar de a definição ser simples, encontrar números primos é um processo complicado. Por exemplo, pense em um número primo que você conhece. Provavelmente você pensou em alguns dos seguintes números: 2, 3, 5, 7, 11, 13. Mas você conseguiria pensar em um número primo de 3 dígitos? E de 6 dígitos? Complicado, não? Nessas horas, o computador é uma ferramenta não apenas útil mas necessária. Com o avanço da computação, podemos realizar testes exaustivos, ou seja, verificar se uma gama de números é primo ou não.
Verificar se um número primo é fácil computacionalmente. Precisamos verificar se algum número, a partir de 2, divide o número desejado. Por exemplo, se queremos saber se 35 é primo, testamos a divisão de 35 por 2, por 3, por 5 e assim sucessivamente. Se achamos um número que divide 35 (no caso, o número 5), então 35 não é primo. Se o único número que divide 35 é ele mesmo (não testamos a divisão por 1, obviamente), então 35 é número primo. Na verdade, podemos parar essa verificação na raiz quadrada desse número, mas falaremos disso mais tarde.
Não se tem, até hoje, uma fórmula para calculá-los. Então, como encontramos os números primos? Simples: verificamos se cada número dado é primo. Começamos pelo número 2, por exemplo. É primo? Sim. Anotamos esse número. Próximo: 3 é primo? Sim e anotamos. Próximo: 4 é primo? Não e não anotamos. Repetimos esse processo até um número máximo a ser testado.
Computacionalmente falando, cada número primo é armazenado em um vetor e, para cada número novo a ser testado, verificamos a divisão pelos números do vetor de números primos.
Uma dica: não precisamos analisar se os números pares são primos porque sabemos que são divisíveis por 2. Logo, verificamos apenas os números ímpares. Vamos exemplificar esse método com o número máximo 35. Escrevemos um vetor de números ímpares de 3 a 35:
| 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 |
Não é necessário escrever o número 2, pois sabemos que é primo e não precisamos testar divisão sobre ele, pois já excluímos todo número par. Vamos começar a verificação:
_3 é número primo? Sim. Armazenamos no vetor de número primos.
| 3 |
_5 é número primo? Vamos verificar: testa a divisão por 3 - não é divisível. Então 5 é primo e armazenamos no vetor de número primos.
| 3 | 5 |
_7 é número primo? Vamos verificar: testa a divisão por 3 - não é divisível. Testa a divisão por 5 - não é divisível. Então 7 é primo e armazenamos no vetor de número primos.
| 3 | 5 | 7 |
_9 é número primo? Vamos verificar: testa a divisão por 3 - é divisível. Então 9 não é primo e passamos para o próximo número (11).
O processo é repetido até acabar o vetor de números a serem testados. Esse processo é bem trabalhoso à mão, mas computacionalmente é bem rápido.
Vamos implementá-lo no R. Começamos criando o vetor de número a serem testados. Vamos criar um vetor de números ímpares de 3 a 101, como vemos abaixo.
v_num = seq(3,101,by=2);
> v_num
[1] 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
[20] 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77
[39] 79 81 83 85 87 89 91 93 95 97 99 101
v_primos = NULL;
v_primos[1] = 3;
Para facilitar nossa programação, já inseri o número 3 no vetor. Como não há numeros pares, é desnecessário armazenar o 2 nesse vetor. Ao final do algoritmo, retornamos para o usuário esse vetor mais o número 2. (na verdade, estamos otimizando o algoritmo, uma vez que evitamos fazer o cálculo da divisão por 2 no teste de cada número).
Agora, para cada número no vetor v_num, verificamos a divisão por cada número do vetor v_primos. Se há alguma divisão exata, o número testado não é primo. Caso contrário, é primo e o armazenamos no vetor v_primos. Fazemos isso com comandos de repetição:
count = 1;
while(count<=length(v_num)){
testa_primo = T;
for(i in 1:length(v_primos)){
if(v_num[count]%%v_primos[i]==0){
testa_primo = F;
break;
}
}
if(testa_primo==T) v_primos = c(v_primos,v_num[count]);
count = count + 1;
}
Note que consideramos, inicialmente, que o número testado é primo (testa_primo = T). Caso haja alguma divisão exata do número por algum dos números do vetor v_primos, então o número testado não é primo, computamos testa_primo = F e saímos do loop, pois já verificamos que o número não é primo (e, portanto, não é necessário mais testes de divisão). Caso não haja divisão exata por nenhum número do vetor v_primos, então o número testado é primo e o acrescentamos no vetor v_primos.
Se executarmos o código acima, calculamos os números primos de 3 a 101. Ao final, acrescentamos o número 2 ao vetor v_primos para retornar o resultado ao usuário, como vemos abaixo:
v_primos = c(2,v_primos)
v_primos
> v_primos
[1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
[20] 71 73 79 83 89 97 101
Pronto! Temos um algoritmo para calcular números primos de 2 a um número máximo. Porém, nosso código está meio solto. Vamos construir uma função:
calcula_primos = function(num_max){
v_num = seq(3,num_max,by=2);
v_primos = NULL;
v_primos[1] = 3;
count = 1;
while(count<=length(v_num)){
testa_primo = T;
for(i in 1:length(v_primos)){
if(v_num[count]%%v_primos[i]==0){
testa_primo = F;
break;
}
}
if(testa_primo==T) v_primos = c(v_primos,v_num[count]);
count = count + 1;
}
v_primos = c(2,v_primos)
return(v_primos)
}
O argumento num_max da função é o valor máximo do vetor de números ímpares. Vamos testar nossa função com num_max igual a 50.
> calcula_primos(50)
[1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
No próximo post vamos otimizar esse código e torná-lo interativo com o usuário.
Até a próxima aula!
Nenhum comentário:
Postar um comentário