/* LISTA 1 (PARTE 2), MA-553/A – Exercício 1 (MONOGRAFIA) */
/* Pedro Thiago Ezequiel de Andrade (RA 063696) */
/* Rafael Lucas Gregório D’Oliveira (RA 063824) */
/* O código abaixo implementado em C busca primos p com a+1<p<r, sendo a e r
parâmetros dados, tais que ap-1-1 é divisível por p2. O algoritmo é bem simples, consiste
em identificar quais que são todos os números primos menores que r por meio do Crivo
de Erastóstenes e verificar quais dentre os primos no intervalo pedido são tais que seu
quadrado dividem ap-1-1. Testamos valores de a entre 2 e 20000 com r=40000. O único
resultado encontrado foi para a=3 e r>11, indicando que 121 divide 310-1 e que a
propriedade pedida não ocorre para outros números dentre os limites testados. Curioso.
*/
#include <stdio.h>
#include <math.h>
int main() {
int a , r , i , j , inicio , l1 , l2 , p , livre=0; //a, r são como descritos no enunciado; l1 e l2
são os limites dos índices do vetor P (abaixo) para os quais se testará se o primo satisfaz
a propriedade pedida; livre indica a posição no vetor R.
int P[100000], R[100]; // P[i] é 1 se 2*i+3 for primo ; R guarda os valores de p que são
satisfatórios dado certo a.
printf("Fornecer valores de 'a' e 'r' na ordem: ");
scanf("%d %d", &a, &r);
//Preenchimento do crivo de Erastóstenes
for (i=0 ; i<(r-3)/2 ; i++)
P[i]=1;
for (i=0 ; i<(sqrt(r)-3)/2 ; i++)
if (P[i]==1) {
inicio=((2*i+3)*(2*i+3)-3)/2;
for(j=inicio; j<(r-3)/2 ; j+=(2*i+3) )
P[j]=0;
}
// fim do preenchimento do crivo, todos os primos menores que r foram identificados.
if(a%2==1) l1=(a-1)/2; else l1=(a/2);
l2=(r-3)/2;
// l1 e l2 representam os limites dos índices em P que devem ser utilizados para que
somente primos p em a+1<p<r sejam testados.
// Verificação dos primos no intervalos considerado, armazenando-os em R:
for(i=l1;i<l2;i++) {
p=2*i+3; // p : impar na posição 'i' no vetor P.
if( (P[i]==1) && ( ((int)pow(a,(p-1))-1)%(p*p)==0) ) {
R[livre]=p;
livre++;
}
}
// retornando os primos satisfatórios para o valor de a considerado:
for(i=0;i<livre;i++)
printf("%d ", R[i]);
}