S'il vous plaît aidez-moi ... est ma mise en œuvre pour compter les nombres premiers en Java faire ce qu'il devrait faire?

Question

J'ai reçu une description de la façon dont je dois implémenter un générateur de nombres premiers utilisant Java; mais je ne suis pas sûr si je le fais correctement. J'espérais que quelqu'un pourrait me donner des conseils généraux pour améliorer ma mise en œuvre! S'il vous plaît, ne me donnez pas de réponse car c'est un travail à faire et j'aimerais le faire moi-même/devenir un meilleur programmeur/ne pas tricher!

Je vais poster la description et ma solution ci-dessous, fondamentalement je voudrais juste savoir quelques choses générales - ai-je suivi les instructions correctement (le plus important car je trouve la langue utilisée un peu confuse) et si je pouvais faire mon programme mieux (si oui, quelques conseils généraux seraient bien pour que je puisse comprendre comment ... Je pense que mon utilisation du logarithme est loin, mais je ne peux pas trouver une meilleure façon de l'utiliser)!

Excuses si cela n'est pas autorisé - si ce n'est pas le cas, ignorez ou supprimez! Merci beaucoup pour votre aide! :)

Description:

Prime (int initialCapacity): Le constructeur de classe . Le but du constructeur est de calculer et de stocker la première capacité initiale & # 56256; first initialCapacity premierfirst initialCapacity primefirst i nombres. L'idée est que vous calculez les nombres une fois et les stocker si que vous pouvez les réutiliser plusieurs fois. Vous devez utiliser un ArrayList pour stocker les nombres premiers. Un algorithme pour calculer les nombres premiers est fourni dans la section suivante.

1. Commencez avec une liste vide de nombres premiers. Vous pouvez représenter cette liste en utilisant une ArrayList.

2. Bien que la taille de ArrayList ne soit pas égale à n, considérez le prochain nombre premier candidat . Initialement, le nombre premier candidat suivant devrait être 2, mais sinon, il devrait être le successeur du candidat précédent nombre premier.

3. Si le nombre premier candidat est un nombre premier, ajoutez-le à la liste.

4. Passez à l'étape 2.

Notez que cet algorithme suggère que vous devez utiliser une boucle while. L'étape 3 de l'algorithme précédent exige que vous connaissiez pour savoir si un premier candidat, c> 1, est un nombre premier . En fait, la dénomination des nombres premiers déjà suggère un algorithme naïf. Pour l'exemple , vous pouvez utiliser une boucle while à pour vérifier que c% i 6 = 0 pour tous les entiers positifs tels que 1 < i et i < c. Cependant, il n'est pas difficile de voir que une bien meilleure méthode est de s'assurer que c% p 6 = 0 pour tous les nombres premiers p tels que p < c. En utilisant les nombres premiers dans votre ArrayList c'est facile comme tarte.est méthode est la méthode que vous êtes censé utiliser. Notez encore que cette suggère que vous utilisiez une boucle while. Enfin, votre mise en œuvre devrait être ecient et ne devrait pas gaspiller les contrôles de la forme c% p 6 = 0 ou c% p = 0. Donc, vous devriez cesser de cirer dès que c% p = 0 pour certains de les nombres premiers dans ArrayList.

Ma solution est la suivante:

import java.util.*; 
public class Prime { 

    public static void main(String[] args){ 

    } 
    public static void prime(int initialCapacity){ 
    int index=2; 
    int logOfInitialCapacity = initialCapacity/(int)(Math.log(initialCapacity)); 
    ArrayList<Integer> listOfPrimeNumbers = new ArrayList<Integer>(logOfInitialCapacity); 
    boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults to 
    // false 

    for (int i=0;i==initialCapacity;i++) { 
     isPrimeNumber[index] = true; 
     } 
     while (index <= listOfPrimeNumbers.size()) 
     { 
     if (isPrimeNumber[index]) { 
      listOfPrimeNumbers.add(index); 
     } 
     for (int j = index; j * index <= initialCapacity; j++) { 
      isPrimeNumber[index * j] = false; 
     } 
     // Now mark the multiple of i as non-prime number 
     index++; 
     } 
    } 

} 

qui devrait calculer la première initialCapacity des nombres premiers et les enregistrer dans un arrayList que la question demande ... Je ne suis pas sûr si je fait exactement comme la question le dit. C'est probablement plus un produit d'étudier toute la journée et d'être un peu usé qu'autre chose!

Merci beaucoup pour votre aide et pour avoir lu tout ceci; désolé pour le long message.

Answer 1

Votre solution ne correspond pas vraiment à la description du problème. La description du problème prescrit un test de primalité (c'est-à-dire un premier candidat, tester s'il est premier). Il veut également initialCapacity nombres premiers.

Les problèmes avec votre solution:

1. il semble essayer d'effectuer tamiser
2. il est inefficace, car les multiples d'un nombre composite sont barrés.
3. il trouve les nombres premiers jusqu'à initialCapacity (pas les premiers nombres premiers initialCapacity - pour voir la différence, essayez initialCapacity = 1).

Answer 2

Vous pouvez répondre à votre question avec ceci:

http://primes.utm.edu/lists/small/1000.txt

Si ceux-ci ne sont pas dans votre liste, votre code ne fait pas correctement.

Vous voulez lire ceci:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes