Cómo encontrar si la suma de divisores de un número es primo o no

Answer 1

Para [math] n \ in \ mathbb N [/ math], deje

[matemáticas] \ sigma (n) = \ displaystyle \ sum_ {d \ mid n} d [/ matemáticas]

denota la suma de todos los divisores positivos de [math] n [/ math].

El hecho de que [math] \ sigma [/ math] es una función multiplicativa [math] (\ sigma (mn) = \ sigma (m) \ cdot \ sigma (n) [/ math] siempre que [math] \ gcd (m , n) = 1) [/ math] y la observación de que [math] \ sigma (n)> 1 [/ math] para [math] n> 1 [/ math] implica que [math] \ sigma (n) [ / math] es primo solo si [math] n = p ^ {\ alpha} [/ math] para algunos primos [math] p [/ math] (de lo contrario [math] n = 1 [/ math] o [math] n [/ math] tiene al menos dos factores primos , de modo que [math] n = ab [/ math], [math] \ gcd (a, b) = 1 [/ math], [math] a> 1 [/ math ], [matemáticas] b> 1 [/ matemáticas] y [matemáticas] \ sigma (n) = \ sigma (a) \ cdot \ sigma (b)) [/ matemáticas].

Además, suponga que [math] n = p ^ {\ alpha} [/ math], donde [math] p [/ math] es primo . Si [math] \ alpha [/ math] es [math] impar [/ math], entonces

[matemáticas] \ sigma (p ^ {\ alpha}) = 1 + p + p ^ 2 + \ cdots + p ^ {\ alpha} = (1 + p) (1 + p ^ 2 + \ cdots + p ^ { {\ alpha} -1}) [/ math].

Por lo tanto, [math] \ sigma (p ^ {\ alpha}) [/ math] es primo implica que [math] \ alpha [/ math] es par . En otras palabras, una condición necesaria para que [math] \ sigma (n) [/ math] sea primo es que [math] n = p ^ {2 \ beta} [/ math], donde [math] p [/ math ] es primo .

Entonces, el problema se reduce a pedir pares [math] (p, \ alpha) [/ math], con [math] p [/ math] prime y [math] \ alpha [/ math] un número entero positivo para el cual

[matemáticas] \ sigma (p ^ {\ alpha}) = 1 + p + p ^ 2 + \ cdots + p ^ {\ alpha} [/ matemáticas]

es primo

Esto es lo mejor que se puede hacer, por lo que puedo ver. El Bot sugiere 4 = 2 ^ 2, 9 = 3 ^ 2, 16 = 2 ^ 4, 25 = 5 ^ 2, 64 = 2 ^ 6, 289 = 17 ^ 2 y 729 = 3 ^ 6, entre otros, como soluciones

Answer 2

Tenga en cuenta que estos también son poderes de un solo primo. Si intenta derivar la fórmula para la suma de los divisores de un número, podrá ver por qué es necesario. Más allá de eso, el exponente también debe ser uno menos que un primo ( Editar : este primo también tiene que ser impar, excepto cuando el primer primo es 2), pero incluso eso no será una condición suficiente.

Estos trucos reducirán drásticamente su espacio de búsqueda, pero aún tendrá que probar cada respuesta potencial. Estoy bastante seguro de que no hay una solución de forma cerrada aquí.

Editar: Aquí está la prueba de todas las afirmaciones:
Deje que [math] x = p_1 ^ {q_1} p_2 ^ {q_2} … p_n ^ {q_n} [/ math] sea la factorización prima de x.
Luego, la suma de sus divisores, [matemáticas] \ sigma (x) = \ frac {(p_1 ^ {q_1 + 1} -1) (p_2 ^ {q_2 + 1} -1) \ dots (p_n ^ {q_n + 1 } -1)} {(p_1-1) (p_2-1) \ dots (p_n-1)} [/ math].
Es fácil ver por qué solo un primo debe estar presente en la factorización.
Yendo más lejos, deje que [math] x = p ^ {(r_1-1) (r_2-1)} [/ math].
Entonces, [matemáticas] \ sigma (x) = \ frac {(p ^ {r_1 r_2} -1)} {(p-1)} = (1 + p + p ^ 2 + \ dots + p ^ {r_1- 1}) (1 + p ^ {r_1-1} + (p ^ {r_1-1}) ^ 2 \ dots (p ^ {r_1-1}) ^ {r_2-1}) [/ math].
Por lo tanto, reclamar dos.
El tercero viene porque [math] \ sigma (p) = 1 + p [/ math] es par y mayor que 2 para todos los números primos impares.

Answer 3

Como otras respuestas ya han explicado cómo resolver este problema, o cómo encontrar números cuadrados tan perfectos.
Algunos pasos para verificar si la suma del divisor de un número es primo.
1. Encuentra los números primos hasta 10 ^ 7.
2. Los números primos son números impares y los cuadrados perfectos tienen propiedades que la suma de sus divisores es impar, por lo que solo necesitamos verificar los números perfectos.

A continuación se muestra el código que utilicé para resolver este problema.

#include #include #include using namespace std; #define MAX 1000010 int a[MAX+10]={0}; bool prime[MAX*4]; int numPrime=37; int p[100000]; inline void gen_primes() { int i,j,c=0; for(i=2;i<=3*MAX;i++)prime[i]=true; for(i=2;i<=(int)sqrt(4*MAX);i++) if (prime[i]) for(j=i;j*i < 4*MAX;j++) prime[i*j] = false; for(int i=1;i1) prod*=1+n; return prod; } vector pr; void perfect() { pr.push_back(2); for(int i=1;i*i<=MAX;i++) { if(prime[sod(i*i)]) { pr.push_back(i*i); } } } int Binary_Search(int start, int end, int val) { int mid; while(start <= end) { if(val < pr[start]) return start-1; if(val > pr[end]) return end; mid = (start+end) / 2; if(val == pr[mid]) return mid; else if(val < pr[mid]) end = mid-1; else start = mid+1; } return numPrime; } int main() { int i,j,tc,A,B; scanf("%d",&tc); gen_primes();pr.clear(); perfect(); while(tc--) { int count=0,count1=0; numPrime=37; scanf("%d%d",&A,&B); count=Binary_Search(0, numPrime-1, A-1); count1=Binary_Search(0,numPrime-1, B); printf("%d\n",count1-count); } } 

Answer 4

Al factorizar, agregar e inspeccionar .

Por razones obvias, un número aquí significa un número compuesto .

Cualquier compuesto no. N puede expresarse como el producto de los poderes de los números primos.

Entonces, N = (p1 ^ a1). (P2 ^ a2)… (pk ^ ak)

[donde p1, p2, …, pk son primos distintos y a1, a2, …, ak son enteros no negativos]

La suma de los divisores de N se puede calcular como

Todo lo que hay que hacer ahora es un poco de factorización, un poco de cálculo y un pequeño examen de si la suma es primo o no.

PD: no estoy seguro de si hay un patrón para eso.

Answer 5

Primero encuentre la suma de los divisores de un no.
Y luego verifique si es primo o no.

A continuación se muestra el algoritmo: –

bool isSumOfDivisorsPrime (int n)
//

int nSqrt <- raíz cuadrada de n
int i <- 2
int nSum <- 1
mientras que yo es menor o igual que nSqrt
hacer
– si divido n
– luego
– – nSum <- nSum + i + n / i
– i ++
if isPrime (nSum)
entonces
– volver verdadero
más
– falso retorno

bool isPrime (int num)
//
si num es igual a 1
entonces
– falso retorno
int nSqrt <- raíz cuadrada de num
para i <- 2 a nSqrt
hacer
– si divide num
– luego
– – rotura
si yo es igual a (nSqrt + 1)
entonces
– volver verdadero
más
– falso retorno