trouver nième nombre premier

J'ai écrit le code suivant ci-dessous pour trouver le n-ième nombre premier. Cela peut-il être amélioré dans le temps de la complexité?

Description:

La liste de tableaux arr magasins le calcul des nombres premiers. Une fois arr atteint une taille "n", la boucle s'arrête et nous récupérer le n-ième élément de la liste de tableaux. Les numéros 2 et 3 sont ajoutés avant les nombres premiers sont calculés, et chaque numéro à partir de 4 est vérifié pour être premier ou non.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); //stores prime numbers 
                                                      //calculated so far
    //add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    //check if number is prime starting from 4
    int counter = 4;
     //check if arr's size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        //dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            //check if current number 'counter' is perfectly divisible from 
           //counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}
Merci de nous donner une description intuitive de ce que votre programme, ou au moins de fournir des commentaires. Nous donnant un bloc de code et de nous demander de les analyser, il est extrêmement difficile pour quiconque de comprendre ce que cela signifie.
Il peut être ouvert à la question de savoir si elle améliore la complexité de calcul, mais un crible d'Eratosthène est un peu rapide de toute façon.
ajout des commentaires de code.
La réponse est stackoverflow.com/a/9704912/849891 .
Aussi, il est bon de rechercher sur le DONC tout d'abord: stackoverflow.com/tags/primes/hot?filter=year .

OriginalL'auteur codewarrior | 2013-02-07

  1. 10

    Oui.

    Votre algorithme de rendre O(n^2) opérations (peut-être que je ne suis pas exacts, mais il me semble),
    où n est le résultat.

    Il y a http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithme qui prend O(ipn* log(log(n))). Vous pouvez faire seulement inp pas, et supposons que n = 2ipn*ln(ipn).
    n devrait juste être supérieure à ipn-prime.
    (nous savons que les distributions de nombres premiers http://en.wikipedia.org/wiki/Prime_number_theorem)

    De toute façon, vous pouvez améliorer les solutions existantes:

    public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}
    pourriez-vous me dire comment cela fonctionne, précisément pourquoi avez-vous vérifier à l'aide de temp*temp? thats va vérifier si le compteur est divisible par 16,25,36..
    Il vérifie temp*temp contre depuis qui implique que les temp <= sqrt(compteur). Il suffit de vérifier jusqu'à ce point, puisque la multiplication est commutative.
    Brillant. merci!
    qu'est-ce que n? qu'est-ce que ipn? inp inp? Est-ce le Crible d'Eratosthène?
    Keegan, nombres premiers à partir de 2. en.wikipedia.org/wiki/Prime_number#Definition_and_examples

    OriginalL'auteur xvorsx

  2. 2

    Quelques choses que vous pouvez faire pour l'accélérer:

    1. Début compteur à 5 et l'incrémenter par 2 au lieu de 1, alors ne pas vérifier les mod 2 dans la boucle.
    2. Au lieu de commencer temp au compteur /2, départ à la première odd <= int(sqrt(compteur))
    3. décrémenter temp par 2.

    Je ne sais pas si ça compte comme l'amélioration de la complexité, mais (2) ci-dessus vont de O(n^2) à O(n*sqrt(n))

    les tests par temp de la sqrt bas est très inefficace. Je le soupçonne même des changements de la complexité pour le pire.
    Il n'est en effet. Je n'ai pas analysé dans le détail, mais le semiprimes dont le plus grand facteur est au moins quatre fois le plus petit facteur, à lui seul donner un supplément de log log n facteur. J'attends que le facteur constant ralentissement est bien pire pour un long temps, même si.
    empiriquement ideone.com/iNxOrC en effet, le comptage-bas code semble fonctionner dans m^1.5, où m est la limite supérieure. Les ratios des temps obtenus sont 2.6x ... 3.6x et de l'aggravation, pour la limite supérieure de 100k ... de 1,2 millions de dollars. m^1.5 pour le comptage-bas code fait réellement sens - il n'y a pas de début de coupure, donc c'est comme si les tests chaque impair par toutes les cotes ci-dessous sqrt. Tout en comptant le coût pour les non-prime de cote est au plus les mêmes que pour les nombres premiers (comme le montre M. O'Neill), en donnant le m^1.5/log(m).
    Qu'entendez-vous par "début" cut-off"? Vous divisez jusqu'à ce que vous trouver le premier diviseur ou atteignent la limite, si vous comptez en haut ou en bas, à cet égard, les deux façons sont similaires. Le compte à rebours, vous avez généralement une façon beaucoup plus long pour le premier diviseur, cependant. Je sorte de s'attendre à Θ(√n) en moyenne (donc le empiriques m^1.5 fits), mais je ne vois pas un moyen facile de le prouver (le plus proche diviseur de √n est plus difficile à saisir que le plus petit diviseur premier).
    c'est ce que je voulais dire, oui, de façon beaucoup plus long est presque "tous les moyens". Il n'est évidemment pas de rigueur dans. Essayez de trouver la "valeur attendue" du facteur le plus important pour un au hasard choisi composite dans la gamme 2..n, quelque chose à cet effet (ce sera notre point de coupure, en moyenne, le compte à rebours). n ou sqrt(n), je m'attends à ne pas faire beaucoup de différence.

    OriginalL'auteur xpda

  3. 0
    public static void Main()
    {
        Console.Write("Enter a Number : ");
        int num;
        int[] arr = new int[10000];
        num = Convert.ToInt32(Console.ReadLine());
        int k;
        k = 0;
        int t = 1;
        for (int j = 1; j < 10000; j++)
        {
            for (int i = 1; i <= j; i++)
            {
                if (j % i == 0)
                {
                    k++;
                }
            }
            if (k == 2)
            {
                arr[t] = j;
                t++;
                k = 0; 
            }
            else
            { 
                k = 0;
            } 
        }
        Console.WriteLine("Nth Prime number. {0}", arr[num]);
        Console.ReadLine();
    }
    Pouvez-vous comprendre une indication de l'amélioration?
    Comment cette [improve] time complexity [of find the nth prime over counting primes identified by trial division]?

    OriginalL'auteur Deepanshu Rathore