Problema

En este proyecto, escribirá un programa Java que lee un entero positivo n de la entrada estándar, luego imprime los primeros n números primos. Decimos que un número entero m es divisible por un número entero distinto de cero d si existe un número entero k tal que m = k d, es decir, si d se divide uniformemente en m. De manera equivalente, m es divisible por d si el resto de m sobre la división (entera) por d es cero. También expresaríamos esto diciendo que d es un divisor de m. Un entero positivo p se llama primo si sus únicos divisores positivos son 1 y p. La única excepción a esta regla es el número 1 en sí mismo, que se considera no primo. Un entero positivo que no es primo se llama compuesto. Euclides mostró que hay infinitos números primos. Las secuencias principales y compuestas comienzan de la siguiente manera:

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … 

Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, … 

Hay muchas formas de probar la primalidad de un número, pero quizás la más simple es simplemente hacer divisiones de prueba. Comience dividiendo m por 2, y si se divide de manera uniforme, entonces m no es primo. De lo contrario, divida entre 3, luego 4, luego 5, etc. Si en cualquier punto se encuentra que m es divisible por un número d en el rango 2 d m − 1, entonces deténgase, y concluya que m es compuesto. De lo contrario, concluya que m es primo. Un momento de reflexión muestra que no es necesario hacer divisiones de prueba por números d que son compuestos. Por ejemplo, si una división de prueba por 2 falla (es decir, tiene un resto distinto de cero, entonces m es impar), entonces una división de prueba por 4, 6 u 8, o cualquier número par, también debe fallar. Por lo tanto, para probar la primalidad de un número m, uno solo necesita hacer divisiones de prueba por números primos menores que m. Además, no es necesario llegar hasta m − 1. Solo es necesario hacer divisiones de prueba de m por primos p en el rango de 2 p m. Para ver esto, suponga que m> 1 es compuesto. Entonces existen enteros positivos a y b tales que 1 <a <m, 1 <b <m, y m = ab. Pero si tanto a> m como b> m, entonces ab> m, contradiciendo que m = ab. Por lo tanto, uno de aob debe ser menor o igual que m.

Para implementar este proceso en Java, escribirá una función llamada isPrime () con la siguiente firma:

static boolean isPrime(int m, int[] P) 

Esta función devolverá verdadero o falso según si m es primo o compuesto. El argumento de matriz P contendrá un número suficiente de primos para hacer la prueba. Específicamente, en el momento en que se llama isPrime (), la matriz P debe contener (al menos) todos los primos p en el rango de 2 p m. Por ejemplo, para probar m = 53 para primalidad, uno debe hacer divisiones de prueba sucesivas por 2, 3, 5 y 7. No vamos más allá desde 11> 53. Por lo tanto, una condición previa para la llamada a la función esPrime (53, P) es que P [0] = 2, P [1] = 3, P [2] = 5 y P [3] = 7. El valor de retorno en este caso sería verdadero ya que todas estas divisiones fallan. De manera similar a la prueba m = 143, uno debe hacer divisiones de prueba por 2, 3, 5, 7 y 11 (ya que 13> 143). La condición previa para la llamada a la función esPrime (143, P) es, por lo tanto, P [0] = 2, P [1] = 3, P [2] = 5, P [3] = 7 y P [4] = 11. El valor de retorno en este caso sería falso ya que 11 divide 143. La función isPrime () debe contener un bucle que atraviesa la matriz P, haciendo divisiones de prueba. Este bucle debe terminar cuando 2 una división de prueba tiene éxito, en cuyo caso se devuelve falso, o hasta que el próximo primo en P sea mayor que m, en cuyo caso se devuelve verdadero. La función main () en este proyecto leerá el argumento de la línea de comando n, asignará una matriz int de longitud n, llenará la matriz con primos, luego imprimirá el contenido de la matriz en stdout de acuerdo con el formato que se describe a continuación. En el contexto de la función main (), nos referiremos a esta matriz como Primes []. Así, array Primes [] juega un doble papel en este proyecto. Por un lado, se utiliza para recopilar, almacenar e imprimir los datos de salida. Por otro lado, se pasa a la función isPrime () para probar nuevos enteros para primalidad. Siempre que isPrime () devuelva verdadero, la prima recién descubierta se colocará en la posición adecuada en la matriz Primes []. Este proceso funciona ya que, como se explicó anteriormente, los primos necesarios para probar un rango entero m solo hasta m, y todos estos primos (y más) ya estarán almacenados en la matriz Primes [] cuando se prueba m. Por supuesto, será necesario inicializar Primes [0] = 2 manualmente, luego proceder a la prueba 3, 4, ... para primalizar usando la función isPrime ().

El siguiente es un resumen de los pasos a realizar en la función main ().

Compruebe que el usuario proporcionó exactamente un argumento de línea de comando que puede interpretarse como un entero positivo n. Si el argumento de la línea de comando no es un entero positivo único, su programa imprimirá un mensaje de uso como se especifica en los ejemplos a continuación, luego saldrá.Asigne matrices Primes [] de longitud n e inicialice Primes [0] = 2.Ingrese un bucle que descubrirá primos posteriores y los almacenará como Primes [1], Primes [2], Primes [3], ..., Primes [n −1]. Este bucle debe contener un bucle interno que recorre los enteros sucesivos y los prueba para determinar su primordial llamando a la función isPrime () con los argumentos apropiados.Imprima el contenido de la matriz Primes [] en stdout, 10 en una línea separada por espacios individuales. En otras palabras, Primes [0] a Primes [9] irán a la línea 1, Primes [10] aunque Primes [19] irán a la línea 2, y así sucesivamente. Tenga en cuenta que si n no es un múltiplo de 10, entonces la última línea de salida contendrá menos de 10 primos.

Su programa, que se llamará Prime.java, producirá una salida idéntica a la que se muestra a continuación. (Como de costumbre,% significa la solicitud de Unix).

% java Prime 
Usage: java Prime [PositiveInteger] 
% java Prime xyz 
Usage: java Prime [PositiveInteger] 
% java Prime 10 20 
Usage: java Prime [PositiveInteger] 
% java Prime 75 
2 3 5 7 11 13 17 19 23 29 
31 37 41 43 47 53 59 61 67 71 
73 79 83 89 97 101 103 107 109 113 
127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 
233 239 241 251 257 263 269 271 277 281 
283 293 307 311 313 317 331 337 347 349 
353 359 367 373 379 
% 
3 

Como puede ver, los argumentos de línea de comando inapropiados generan un mensaje de uso que es similar al de muchos comandos de Unix. (Intente ejecutar el comando more sin argumentos para ver dicho mensaje). Su programa incluirá una función llamada Usage () con firma

static void Usage() 

que imprime este mensaje en stderr, luego sale. Por lo tanto, su programa contendrá tres funciones en total: main (), isPrime () y Usage (). Cada uno debe ir precedido de un bloque de comentarios que indique su nombre, una breve descripción de su funcionamiento y cualquier condición previa necesaria (como las de isPrime ()). Vea ejemplos en la página web.

Intento de solución

class Prime {
    public static void main(String[] args) {
        int num1 = 0;
        int num2 = 0;
        int num3;
        for (num1 = 1; num1 < 101; num1++)
            System.out.println(num1);
        for (num2 = 1; num2 < 101; num1++)
            System.out.println(num2);
        num3 = num2 % num1;
        if (num3 == 0)
            System.out.println("The prime numbers are " + num1);
        else
            System.out.println("The prime numbers are " + (num1 += 1));
    }
}