De volta aos números primos
Continuação do post anterior
O tema do post anterior gerou algumas discussões em sala de aula, embora o tema seja o calculo do PI, parece que o que mais “pegou” foi o envolvimento com os números primos, depois de alguma pesquisa, fiquei particulamente interessado, por isto resolvi abstrair o pi (embora já tenha desenvolvido uma versão que utiliza o algoritmo de Leibniz, que dispensa a utilizacao do números primos –fica para um post no futuro- ) e me concentrar em um algoritmo de “primalidade”, existem “teracentos” na rede, a grande maioria exatamente como o da minha primeira versão, ou seja, pegando o número que se deseja saber se é primo e ir checando se há divisores. O problema deste algoritmo é a lentidão.
Como determinar se um número é primo
O primeiro raciocíneo que vem à cabeça dos simples mortais (como eu!) é ver se o número é um número par diferente de 2, se sim ele já é descartado, se for 2 é primo, depois é só ir dividindo pelos números subsequentes a ele até chegar a ele menos 1, se alguma das divisões resultar resto 0 (zero) então o número não é primo, o problema desta lógica quando convertemos em um algoritmo para ser executado em um computador, é custo computacional, tomanos o numero 1.000.000, teriamos que testar a divisão 500.00 vezes (excluindo os pares).
Otimizando o algoritmo
Todo número composto (não primo) é um produto de números primos, por exemplo: 120 é um número composto da seguinte maneira: 2^3x3x5, ou 2x2x2x3x5, ou seja, todo número composto tem um primo como divisor, por outro lado, nenhum número primo tem outro primo como divisor, a não ser ele mesmo, então bastaria saber se o número tem algum primo como divisor para saber que ele não é primo.
Otimizando ainda mais
Como a raiz quadrada é uma espécie de divisor da imagem de um número, qualquer número terá a mesma quantidade de divisores antes de sua raiz, exatamente igual aos divisores após a sua raiz, vamos considerar o numero 144, cuja raiz é 12:
Divisores antes da raiz: 2, 3, 4 , 6, 8 e 9
É facil perceber que o próximo divisor depois da própria raiz será o resultado da divisão do número considerado, pelo último divisor antes da raiz, neste caso 144/9 = 16, o próximo divisor é exatamente o resultado da divisão do número (144) pelo antepenúltimo divisor anterior à raiz, ou seja: 144/8 = 18 e assim sucessivamente até atingir ao primeiro divisor, no caso o 2 que ”olhando no espelho” se torna 72, resultado da contra 144/2. Tudo isto para mostrar que se um número não tiver divisores primos até a sua raiz, seguramente não terá após a mesma, então para sabermos se um número é primo ou não, basta procurarmos por divisores até a sua raiz, em vez de ficar procurando por toda a sua “extensão”. No caso de testarmos o número 1.000.000, poderiamos testar a divisibilidade pelos impares até a raiz que é 1.000, neste caso testarimos aproximadamente 500 vezes, e não 500.000.
Explicando o novo código
Depois de várias horas de pesquisa sobre a explanação acima um novo codigo foi desenvolvido, desta vez somente para “gerar” números primos, tantos quantos forem o número informado pelo usuário no primeiro input do programa, o algoritmo funciona da seguinte forma: há uma tabela com os primeiros 55 números primos pré-computados, o primeiro loop dentro de main, pega o número (que se quer determinar se é primo) e chama a função eh_primo() que vai dividindo pelos primos desta tabela, se houver divisão exata, que não seja por um dos números da tabela, então a função retorna falso. A função eh_primo permite testar até o numero 4177, com este numero de testes, podemos gerar 474 numeros primos, sendo o ultimo o próprio numero 4177.
Depois do primeiro loop “For” da função eh_primo()
Se o codigo passar a função eh_primo(), é calculada a raiz quadrada do número e então, em um loop, dividimos o número pelos impares entre 3 a propria raiz, se não houver nenhum divisor, á função retorna true, indicando a primalidade.
Codigo:
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 | <pre> #include <math.h> #include <time.h> #include <stdio.h> #include <stdlib.h> long int entradas = 0, val_max, val_n = 1, val_max_259 = 0; float time_waste(time_t start, time_t end); // Variaveis globais char tics[12] = "Segundo(s)"; // Prototipos: int eh_primo(unsigned int n); float time_waste(time_t start, time_t end); int main() { unsigned int count = 1, primo = 1, n; time_t start, end; start = time(NULL); printf("\n"); system("cls"); printf("Entre com o numero de primos : "); scanf("%i",&n); while (primo <= n) { count++; if (eh_primo(count) == 1) { printf("%d\t", count); if (primo++ % 10 == 0) printf("\n"); } } end = time(NULL); printf("\ntempo gasto: %f, %s\n", time_waste(start, end), tics); fflush(stdin); getch(); } int eh_primo(unsigned int n) { unsigned int i; static unsigned int primes55[] = {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}; // Checa divisibilidade do numero pelos primos acima for (i = 0; i < 55; i++) { if (n % primes55[i] == 0) { if (n == primes55[i]) return 1; else return 0; } } // extrai raiz do numero n unsigned int raiz_n = sqrt(n); // Se o numero é para é é descartado antecipadamente if (n % 2 == 0) return 0; // Verifica se tem algum divisor entre 3 e a raiz do proprio numero for (unsigned int i = 3; i < raiz_n; i += 2) { if (n % i == 0) return 0; } return 1; } // Calculo do tempo gasto (gastando mais tempo :/ ) float time_waste(time_t start, time_t end) { float tempo_gasto; tempo_gasto = (difftime(start, end)*-1); // POG tempo_gasto = (tempo_gasto < 1) ? (0.1) : tempo_gasto; if (tempo_gasto > 59) { tempo_gasto = (tempo_gasto / 60); strcpy(tics, "Minuto(s)"); } if (tempo_gasto > 59) { tempo_gasto = (tempo_gasto / 60); strcpy(tics, "Hora(s)"); } return tempo_gasto; } |
July 24th, 2011 at 8:34 pm
Veja singelo video sobre os 15 primeiros primos em http://www.youtube.com/watch?v=ZLorvAkyMA0