Contador directo de números primos [cerrado]

Si quieres hacer trampa, entonces, por todos los medios, genera los números primos fuera de línea, colócalos en una memoria y descárgalos, será más rápido y fácil. ¿Pero sería genial? No lo creo.

Este es un paso hacia una posible respuesta. Sería bueno si funcionara perfectamente. Tal como está, casi funciona, por lo que es bastante genial. Para saber cómo solucionarlo, vea el final de la respuesta.

No hay tablas de búsqueda para generar, la solución realmente calcula los números primos, utilizando solo contadores y puertas. No es necesario encontrar reglas específicas para los bits.

Lo realmente interesante de esto es que el límite de 63 establecido en el OP es un límite flexible en esta solución. Es trivial y obvio cómo extender la solución a un límite arbitrario, que es un límite determinado por sus fondos.

Si bien esta implementación puede ser nueva, la idea retrocede un poco. De hecho, antes de 200 BCE, a Eratóstenes .

Un número P es primo si no tiene factores (aparte del trivial 1 y P). Un número mP tiene factores m y P. Si crea un contador de estado P (también conocido como contador de módulo), reinícielo a cero y crónelo una vez, su salida será 1, dos veces y será 2, P veces y volverá a 0 otra vez, mP veces y su salida también volverá a 0.

Esto nos permite ver si un número tiene algún factor P. Registre dos contadores al mismo tiempo, uno contando hasta al menos Nmax para generar un número N, el otro contando con el módulo P. Cuando la salida de este último es cero, P divide N.

Si un número compuesto N tiene dos factores, uno de ellos siempre será \ $ < \ sqrt N \ $. Declararé esto sin pruebas, que dejaré como un ejercicio para el lector. Eso significa que para números de hasta 64, solo necesitamos pruebas con factores primos menores de 8 o 2, 3, 5 y 7.

Construimos 5 contadores. El contador N, que cuenta hasta por lo menos 63. Luego construimos 4 contadores de módulo de longitud 2, 3, 5 y 7 cuentas. Esto se puede hacer de varias maneras, la más obvia de las cuales es decodificar las salidas de los contadores y restablecer el contador cuando alcance nuestro conteo objetivo.

A medida que el contador de N cuenta arriba, si alguno de los contadores de módulo está en 0, N tiene un factor y no puede ser primo. Por lo tanto O Juntos, todas las pruebas para los contadores de módulo son cero, y llamamos compuesto si alguno es cero.

Aquí hay una hoja de cálculo que muestra los resultados de la implementación de este algoritmo para N hasta 63

N   P2  P3  P5  P7  prime
0   0   0   0   0   FALSE
1   1   1   1   1   TRUE
2   0   2   2   2   FALSE
3   1   0   3   3   FALSE
4   0   1   4   4   FALSE
5   1   2   0   5   FALSE
6   0   0   1   6   FALSE
7   1   1   2   0   FALSE
8   0   2   3   1   FALSE
9   1   0   4   2   FALSE
10  0   1   0   3   FALSE
11  1   2   1   4   TRUE
12  0   0   2   5   FALSE
13  1   1   3   6   TRUE
14  0   2   4   0   FALSE
15  1   0   0   1   FALSE
16  0   1   1   2   FALSE
17  1   2   2   3   TRUE
18  0   0   3   4   FALSE
19  1   1   4   5   TRUE
20  0   2   0   6   FALSE
21  1   0   1   0   FALSE
22  0   1   2   1   FALSE
23  1   2   3   2   TRUE
24  0   0   4   3   FALSE
25  1   1   0   4   FALSE
26  0   2   1   5   FALSE
27  1   0   2   6   FALSE
28  0   1   3   0   FALSE
29  1   2   4   1   TRUE
30  0   0   0   2   FALSE
31  1   1   1   3   TRUE
32  0   2   2   4   FALSE
33  1   0   3   5   FALSE
34  0   1   4   6   FALSE
35  1   2   0   0   FALSE
36  0   0   1   1   FALSE
37  1   1   2   2   TRUE
38  0   2   3   3   FALSE
39  1   0   4   4   FALSE
40  0   1   0   5   FALSE
41  1   2   1   6   TRUE
42  0   0   2   0   FALSE
43  1   1   3   1   TRUE
44  0   2   4   2   FALSE
45  1   0   0   3   FALSE
46  0   1   1   4   FALSE
47  1   2   2   5   TRUE
48  0   0   3   6   FALSE
49  1   1   4   0   FALSE
50  0   2   0   1   FALSE
51  1   0   1   2   FALSE
52  0   1   2   3   FALSE
53  1   2   3   4   TRUE
54  0   0   4   5   FALSE
55  1   1   0   6   FALSE
56  0   2   1   0   FALSE
57  1   0   2   1   FALSE
58  0   1   3   2   FALSE
59  1   2   4   3   TRUE
60  0   0   0   4   FALSE
61  1   1   1   5   TRUE
62  0   2   2   6   FALSE
63  1   0   3   0   FALSE

Esta es la ecuación de la columna principal en la línea N = 62

=not(or(B62=0, C62=0, D62=0, E62=0))

Inmediatamente ves la falla. Sí marca 1 como primo, aunque pierde 2, 3, 5 y 7.

¿Por qué? ¡Porque para esos números primos, el contador de módulo es cero!

Hay varias correcciones posibles.

Uno es un cambio de definición, que me parece un poco barato. Genera todos los primos excepto los primos hasta sqrt (Nmax).

Otra es incluir una decodificación de esos números primos faltantes. Como solo hay un número pequeño, esto puede ser razonable, pero es feo y arruina la extensión a un límite arbitrario por el que estaba tan entusiasmado.

El tercero, y en mi opinión la mejor solución, es agregar un pestillo adicional por contador de módulo, que se reinicia inicialmente, y se establece cuando el contador se desplaza por primera vez. Use esto para enmascarar el cero ofensivo que produce el contador. De hecho, esto representa una implementación lógica del lenguaje del Tamiz de Eratóstenes, de poner el primero de cada número primo en la tabla. La ventaja de esto es que todos los canales de módulo son idénticos, además de la longitud del contador, lo que restablece la trivialidad de extender la solución a Nmax arbitrario.

¿Quizás necesitas un contador que produzca solo los números primos en secuencia? Envuelva un oscilador de reloj y una compuerta de habilitación alrededor de este contador, de modo que cuente rápidamente para omitir cualquier número compuesto y detenerse en los números primos. Agregue un pestillo de salida si realmente no quiere ver esos números compuestos parpadeando en la salida.

Recopilando bits de los comentarios ...

De manera realista, la solución más simple será un contador binario directo, con las salidas del contador actuando como entradas de dirección a una ROM.

Hay solo 18 números primos en tu rango, por lo que es un contador de 5 bits. Por lo tanto, la ROM necesita al menos 5 bits de dirección y al menos 6 bits de datos.

Tendrás que averiguar qué hacer cuando llegues al final. Tal vez use un bit de datos de repuesto en la ROM para codificar "fin de secuencia" y utilícelo para restablecer el contador a cero.

Si puede encontrar una fórmula general para calcular el siguiente número primo, le sugiero que lo escriba y lo envíe a un diario matemático. Alguien probablemente te nominará para la medalla Fields.