Sabemos que existem infinitos números primos. Mas, como podemos determinar se um número natural $n$ é primo ou composto? Uma possibilidade é testar candidatos a divisores e exibir um divisor não trivial, isto é, um divisor diferente de $1$ e $n$. Neste post nos restringimos aos divisores inteiros positivos. Mas não precisamos exaurir a lista de todos os inteiros de $2$ até $n-1$. Podemos nos valer do Crivo de Eratóstenes. No nosso caso vamos usar um versão mais fraca.
Proposição [1] Se $n$ é composto então existe um divisor $d$ não trivial tal que $d\leq\sqrt{n}$.
Demonstração.
Suponha por absurdo que $n$ é um número composto e que não possui divisor não trivial menor ou igual do que $\sqrt{n}$. Portanto, existem $a,b \in \mathbb{N}$ tais que $n=a\cdot b$ e $a,b>1.$ Por outro lado, $a>\sqrt{n}$ e $b>\sqrt{n}$, assim, $n=a\cdot b>\sqrt{n}\cdot \sqrt{n}=n $. Contradição. Logo, $n$ possui pelo menos um divisor não trivial menor ou igual do que $\sqrt{n}.\,\,\, \square$
Por outro lado, se $n$ é primo ele não possui divisor não trivial menor ou igual do que $\sqrt{n}$. Então basta buscar candidatos a divisores de $2$ até $[\sqrt{n}]$, onde $[\sqrt{n}]$ é o maior inteiro positivo menor ou igual do que $\sqrt {n}$. Podemos simplificar mais ainda testando o dois e em seguida somente os ímpares da nossa lista restrita. A seguir vamos exibir um código em C que determina se o número é primo ou composto adaptado de um código disponibilizado pelo IME.
Algoritmo
________________________________________________________
#include <stdio.h>
int main()
{
int num,divisor,ehprimo,cont,resultado, resto;
printf("Por favor digite um numero inteiro==>");
scanf("%d",&num);
if((num<=1)||(num!=2 && num%2==0))
{
ehprimo=0;
printf ("\n seu número ou é par e distinto de 2 ou é menor que 2.");
}
else
{
ehprimo=1;
}
divisor=1;
cont=0;
resultado=num;
while((ehprimo==1)&&(divisor<=resultado)&&(num!=2))
{
divisor=divisor+2;
resultado=num/divisor;
resto=num%divisor;
printf("\n candidato a divisor %d, parte inteiro %d",divisor,resultado);
printf(", resto %d ",resto);
cont ++;
if(num%divisor==0)
{
ehprimo=0;
}
else
{
ehprimo=1;
}
}
if((num%2!=0)&&(num>1))
{
printf ("\n foram realizadas %d divisões",cont);
}
if(ehprimo==1)
{
printf("\n %d eh primo", num);
}
else
{
printf("\nO %d nao eh primo.",num);
}
return 0;
}
________________________________________________________
O código funciona, porém, tem custo computacional $O(\sqrt{n}).$
Desafio
2) (OIbM 2014) Dado um conjunto $X$ e uma função $f:X \to X$ denotamos, para cada $x \in X, f^1(x)=f(x)$ e, para cada $j \geq 1, f^{f(j+1)}(x)=f(f^j(x))$. Dizemos que $a \in X$ é um ponto fixo de $f$ se $f(a)=a$. Para cada número real $x$, definimos $\pi(x)$ como o número de primos positivos menores ou iguais a $x$. Dado um número positivo $n$, dizemos que $f:\{1,2,3,...,n\} \to \{1,2,3,...,n\}$ é catracha se $f^{f(k)}(k)=k$ para todo $k\in\{1,2,3,...,n\}$. Prove que:
a) Se $f$ é catracha, então $f$ tem pelo menos $\pi(n)-\pi(\sqrt{n})+1$ pontos fixos.
b) Se $n\geq 36$, então existe uma função catracha com exatamente $\pi(n)-\pi(\sqrt{n})+1$ pontos fixos.
Referências
MAC-110 - Numero Primo - Três solucoes para o mesmo problema. Disponível em: ime.usp.br/~yw/2012/mac110/material/primo.html.
MARTINEZ, F. B. et al. Teoria dos Números: um passeio com primos e outros números. IMPA, Rio de Janeiro, 5ª edição, 2018.
Provas e gabaritos. Disponível em: OBM - Olimpíada Brasileira de Matemática.
Nenhum comentário:
Postar um comentário