Problema

Neste projeto, você escreverá um programa Java que lê um número inteiro positivo n da entrada padrão e depois imprime os primeiros n números primos. Dizemos que um número inteiro m é divisível por um número inteiro diferente de zero d se existe um número inteiro k tal que m = kd, isto é, se d se divide igualmente em m. Equivalentemente, m é divisível por d se o restante de m na divisão (inteira) de d for zero. Também expressaríamos isso dizendo que d é um divisor de m. Um número inteiro positivo p é chamado primo se seus únicos divisores positivos forem 1 ep. A única exceção a essa regra é o próprio número 1, que é considerado não primo. Um número inteiro positivo que não é primo é chamado composto. Euclides mostrou que existem infinitos números primos. As seqüências prime e composta começam da seguinte maneira:

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, … 

Existem muitas maneiras de testar um número de primalidade, mas talvez o mais simples seja simplesmente fazer divisões de teste. Comece dividindo m por 2 e, se dividir uniformemente, então m não é primo. Caso contrário, divida por 3, depois 4, depois 5, etc. Se em algum ponto m for encontrado divisível por um número d no intervalo 2 d m -1, então pare e conclua que m é composto. Caso contrário, conclua que m é primo. Um momento de reflexão mostra que não é necessário fazer nenhuma divisão de teste pelos números d que são eles próprios compostos. Por exemplo, se uma divisão de teste por 2 falhar (ou seja, tiver um restante diferente de zero, então m é ímpar), uma divisão de teste por 4, 6 ou 8, ou qualquer número par, também deverá falhar. Assim, para testar um número m para primalidade, é necessário apenas fazer divisões de teste por números primos menores que m. Além disso, não é necessário ir até m-1. Só é necessário testar divisões de m por números primos p na faixa de 2 p m. Para ver isso, suponha que m> 1 seja composto. Então existem inteiros positivos aeb de modo que 1 <a <m, 1 <b <m em = ab. Mas se a> me b> m, então ab> m, contradizendo que m = ab. Portanto, um de a ou b deve ser menor ou igual a m.

Para implementar esse processo em java, você escreverá uma função chamada isPrime () com a seguinte assinatura:

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

Essa função retornará verdadeiro ou falso, dependendo de m ser primo ou composto. O argumento da matriz P conterá um número suficiente de números primos para fazer o teste. Especificamente, no momento em que isPrime () é chamado, a matriz P deve conter (pelo menos) todos os primos p no intervalo de 2 p m. Por exemplo, para testar m = 53 para primalidade, é preciso fazer divisões de teste sucessivas por 2, 3, 5 e 7. Não avançamos mais desde 11> 53. Portanto, uma pré-condição para a chamada de função éPrime (53, P) é que P [0] = 2, P [1] = 3, P [2] = 5 e P [3] = 7. O valor de retorno nesse caso seria verdadeiro, pois todas essas divisões falham. Da mesma forma que no teste m = 143, é necessário fazer divisões de teste por 2, 3, 5, 7 e 11 (desde 13> 143). A pré-condição para a chamada de função éPrime (143, P) é, portanto, P [0] = 2, P [1] = 3, P [2] = 5, P [3] = 7 e P [4] = 11. O valor de retorno nesse caso seria falso, já que 11 divide 143. A função isPrime () deve conter um loop que percorre a matriz P, fazendo divisões de teste. Esse loop deve terminar quando 2 uma divisão de avaliação for bem-sucedida, caso em que falso é retornado ou até que o próximo primo em P seja maior que m, caso em que true é retornado. A função main () neste projeto lê o argumento da linha de comando n, aloca uma matriz int de comprimento n, preenche a matriz com números primos e imprime o conteúdo da matriz em stdout de acordo com o formato descrito abaixo. No contexto da função main (), nos referiremos a essa matriz como Primes []. Assim, o array Primes [] desempenha um papel duplo neste projeto. Por um lado, é usado para coletar, armazenar e imprimir os dados de saída. Por outro lado, é passado para a função isPrime () para testar novos números inteiros quanto à primalidade. Sempre que isPrime () retornar true, o novo primo descoberto será colocado na posição apropriada na matriz Primes []. Esse processo funciona, pois, como explicado acima, os números primos necessários para testar um intervalo m inteiro até m, e todos esses números primos (e mais) já estarão armazenados na matriz Primes [] quando m for testado. Obviamente, será necessário inicializar Primes [0] = 2 manualmente e, em seguida, prossiga com o teste 3, 4,… quanto à primalidade usando a função isPrime ().

A seguir, é apresentado um resumo das etapas a serem executadas na função main ().

Verifique se o usuário forneceu exatamente um argumento de linha de comando que pode ser interpretado como um número inteiro positivo n. Se o argumento da linha de comando não for um número inteiro positivo único, seu programa imprimirá uma mensagem de uso conforme especificado nos exemplos abaixo e saia.Aloque a matriz Primes [] de comprimento n e inicialize Primes [0] = 2.Digite um loop que descobrirá os primos subseqüentes e os armazenará como Primes [1], Primes [2], Primes [3], ..., Primes [n -1]. Esse loop deve conter um loop interno que percorre inteiros sucessivos e os testa quanto à primalidade chamando a função isPrime () com argumentos apropriados.Imprima o conteúdo da matriz Primes [] em stdout, 10 em uma linha separada por espaços únicos. Em outras palavras, os Primes [0] a Primes [9] vão na linha 1, Primes [10], embora Primes [19] vá na linha 2, e assim por diante. Observe que se n não for múltiplo de 10, a última linha de saída conterá menos de 10 números primos.

Seu programa, que será chamado de Prime.java, produzirá uma saída idêntica à da amostra executada abaixo. (Como sempre,% significa o prompt do 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 você pode ver, argumentos inapropriados da linha de comando geram uma mensagem de uso semelhante à de muitos comandos unix. (Tente executar o comando more sem argumentos para ver essa mensagem.) Seu programa incluirá uma função chamada Usage () com assinatura

static void Usage() 

que imprime esta mensagem para stderr e sai. Assim, seu programa conterá três funções ao todo: main (), isPrime () e Usage (). Cada um deve ser precedido por um bloco de comentários, fornecendo seu nome, uma breve descrição de sua operação e quaisquer pré-condições necessárias (como as de isPrime ().) Veja exemplos na página da web.

Tentativa de solução

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));
    }
}