De volta aos números primos

7:55 pm in Desenvolvimento by Sidon

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;
}