Mirando los números y teniendo en cuenta $n < p < 2n - 2$ $p = 3n\pm 1$ donde $p$ es cualquier número primo, yo era capaz de identificar una propiedad de los números de $c=3n\pm 1$ donde $c$ es un número compuesto:
Deje $P_n$ ser primos donde $P_1 = 3, P_2 = 5,...,P_n=p$.
Cada compuesto $c$ $n \to x$ es de la forma:
- $P_{1 \to n}y$
o
- ${P_n }^2$
Puesto que esto es cierto, sólo $n$ primos de $P_n = \pi(\sqrt{limit})-1$ donde $\pi(x)$ es la principal función de conteo, es necesario identificar todos los números primos $P_n < p < limit$. En ese caso, el número de números primos se utiliza para determinar si $n=p$ son considerablemente menores que en otras funciones que las pruebas de los números primos, y es un poco más elegante, no de fuerza bruta, no aleatoriedad, por ejemplo,
Así que es posible que la búsqueda de números primos de $3,...,\infty$ se podría hacer (si no tiende hacia el infinito, juego de palabras) por la prueba de los números impares de forma consecutiva y el aumento de la $n$ por cada $c = {P_n}^2$.
Para probar esto, necesitaba una función para comprobar si el número es de la forma $3n\pm 1$:
$e_n(x)=\left\{\begin{matrix} 0, & x\pm 1 \not\equiv 0 \: \mod\,3\\ 1, & \end{de la matriz}\right.$
Then I needed to check if the number is composite based on $P_{1 \n}y$:
$k_n(x)=\left\{\begin{matrix} 0, & x \equiv 0 \: \mod\,\forall\in \{ P_1,...,P_{n-1} \}\\ 1, & \end{de la matriz}\right.$
I also needed to check if ${P_n }^2$ where $n = \pi(\sqrt{límite})-1$:
$t_n(x) = \left\{\begin{matrix} 0, & x = \,({P_n}^2)\\ 1, & \end{de la matriz}\right.$
Then I summed it all into one function:
isPrime$_n(x) = t_n(x) \mediados de k_n(x) \mediados de e_n(x),\,\,$ if $\,\, {\pi(\sqrt x)} = n$
Where $\mid$ es el operador lógico and.
De esta manera es fácil crear un algoritmo que los rendimientos de los números primos, y sólo los números primos, sin tamizado o la realización de cálculos complejos.
Ejemplo de pseudo-código:
n = 1: Counts number of primes in use by algorithm
N = {3,5,7,9,...,limit}: All natural odd numbers from 3 to limit
P = {3}: The first odd prime number, the others found are appended
for all numbers x in set N do:
if not t(x,n):
n = n + 1, next
if not k(x,n):
next;
if e(x,n):
Append x to P, next
Este rendimientos de los números primos y sólo los números primos.
He aquí un ejemplo que utiliza Python para generar números primos se basan en este principio: (Por favor excusa de formato incorrecto.)
def k(x,n):
for y in range(n):
if x%primes[y]==0:
return False
return True
def e(x,n):
global primes
def xpm(x):
return x+1,x-1
x = xpm(x)
if not (x[0]%3==0 or x[1]%3==0):
return False
return True
def t(x,n):
global primes
if x!=(primes[n-1]**2):
return True
return False
## The number of primes used, n, is printed as n but;
## if the limit has a prime power close or at the limit,
## like 55, then n is most likely incorrect because
## the next number that is 0 MOD(primes[n-1]) is primes[n-1]*primes[n-2]
primes = [3] ## Start with the first odd prime
n = 1 ## n is 1, since primes[n-1] == 3
## primes[n-1] is 2
limit = 1000 ## The limit of numbers to test if prime
for x in range (5,limit + 1,2): ## For all odd numbers x to limit
if not t(x,n): ## if x % primes[n-1] == 0, then x is composite.
n += 1 ## Increment n, because primes[n-1]**2 was
continue ## encountered, then continue
if not k(x,n): ## if x % primes[0 -> n-1] == 0, then
continue ## x is composite, continue
if not e(x,n): ## if (x+-1) % 3 == 0, then
continue ## x is composite
primes.append(x) ## x is prime so append it to the prime list
print ("Number of primes used to generate "+str(len(primes))+": "+str(n-1))
print ("Largest prime used: "+str(primes[n-1]))
Los rendimientos de los primos de cualquier límite, pero el código no está optimizado, así que no espere tamiz de la velocidad, puesto que es en realidad la prueba de cada número, no sieveing ellos.
Aunque lenta en comparación con la buena tamices, se corrió y terminó en menos de 3 segundos con $limit = 10^6$. Esto resultó en 78497 de los números primos, generados a partir de $P_1,...,P_n$ donde $n = 167 = \pi(\sqrt{limit})-1$, que es el número de números primos menores de $10^6$-1, que representan el 2.
Así que mi pregunta es:
Es bien conocido y entendido desde antes? En ese caso, ¿dónde podría encontrar más información sobre el tema?
Lo pregunto porque después de semanas de investigación, no he encontrado una función, a excepción de los tamices, que no es exactamente de verificación de números de primalidad, que no necesita más de $\pi(\sqrt x)$ prepara para generar una serie de números primos.
Si me he perdido un punto importante que hace que este conocimiento común, por favor, dime lo que puede que se me cayó la picadura de trabajar para nada, en lugar de leer...
Un cordial saludo,
Juan
