De retour de tous les nombres premiers plus petit que M

Étant donné un entier M. retour de tous les nombres premiers plus petits que M.

Donner un algorithme aussi bon que vous le pouvez. Besoin de considérer le temps et l'espace de la complexité.

Tamiser la journée!!!!!

OriginalL'auteur user658266 | 2011-03-18

12

Un couple de performances supplémentaires de conseils:
1. Vous avez seulement besoin de tester jusqu'à la racine carrée de M, puisque tout nombre composé a au moins un facteur premier inférieur ou égal à la racine carrée
2. Vous pouvez mettre en cache des nombres premiers connus comme vous générer et tester des séries ultérieures contre seulement les numéros de cette liste (au lieu de chaque numéro ci-dessous sqrt(M))
3. Vous pouvez bien évidemment faire sauter le même nombre (sauf pour 2, bien sûr)
3. Eh bien, vous ne devriez pas laisser tomber tous! Vous ne devriez pas tomber 2 😉
Je pense d'abord énoncé est faux. Par exemple N = 120. 113 est le premier < N. mais 113 > sqrt (N).
Je ne suis pas sûr de ce que vous essayez de dire. Bien sûr, il pourrait être (indépendantes) de nombres premiers plus grand que la racine carrée de N, mais cela ne veut pas nous dire quelque chose d'utile. Le point est que chaque nombre composé a au moins un facteur premier inférieur ou égal à la racine carrée et vous avez seulement besoin de trouver un tel facteur de prouver que N est composite (c'est à dire il n'y a pas besoin de continuer à vérifier). C'est le point de la première instruction.
Désolé. Je pense peut-être que votre réponse est courte et ressemble à un commentaire au lieu d'une réponse complète. Quand j'ai lu le Wiki Crible d'Eratosthène je comprends votre astuce. Mais parce que votre réponse a été la première chose que j'ai lu de ne pas comprendre ce que l'on vous parle.
Vous avez raison, Mais vous devez comprendre le contexte d'appliquer ce fait. Je ne dis pas que votre réponse est fausse, mais je n'ai pas le comprendre jusqu'à ce que j'ai obtenu le contexte de la réponse, j'étais juste en suggérant à améliorer votre réponse un peu pour les autres utilisateurs d'obtenir une meilleure compréhension, par exemple, je confonds votre N avec M. OP viens Aussi de réaliser même quand on a été la réponse de celui d'Andrew est le plus voté parce que donner othrer les utilisateurs à la recherche de la réponse dans le bon contexte.

OriginalL'auteur Wayne Burkett
18

Le Crible d'Eratosthène est un bon endroit pour commencer.

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

Est-il un moyen facile de faire ce pas de la demande O(n) l'espace?
Il y a d'autres tamis qui sont faciles à comprendre et ne pas la demande O(n) l'espace. Ou vous venez de le faire pour une quantité constante de nombre et plus. Par exemple. vous voulez tous les nombres premiers en dessous de 10000 puis le faire en lots de 100 ou de 1000 à réduire l'utilisation de l'espace et seulement de sauver les nombres premiers par la suite.
O(n) l'espace est beaucoup d'espace à la complexité si N est supérieur, peut-être 2 milliards de dollars ou plus. Le Crible d'Atkin est le meilleur à utiliser.

OriginalL'auteur Andrew Cooper
2

La réponse habituelle est de mettre en œuvre la Crible d'Eratosthène, mais ce n'est vraiment qu'une solution pour trouver la liste de tous les nombres premiers plus petits que N. Si vous voulez tests de primalité pour des numéros, il y a de meilleurs choix pour les grands nombres.

OriginalL'auteur sarnold
2

Crible d'Eratosthène est bon.

OriginalL'auteur user664982
1

π(n) de compter les nombres premiers inférieurs ou égaux à n. Pafnuty de Tchebychev a montré que si

limn→∞ π(n)/(n/ln(n))

existe, il est de 1. Il y a beaucoup de valeurs qui sont à peu près égale à π(n) en fait, comme indiqué dans le tableau.

Il donne droit nombre de nombre premier pour ce format de nombre.J'espère que ce sera utile.

Cela ne répond pas à la question.

OriginalL'auteur Ujjwal
0

je suis un novice programmeur en c# (et de nouveau à S. O.), donc cela peut être un peu verbeux. néanmoins, j'ai testé, et je travaille.

c'est ce que je suis venu avec:
```
for (int i = 2; i <= n; i++)
{
    while (n % i == 0)
    {
        Console.WriteLine(i.ToString());
        n /= i;
    }
}
Console.ReadLine();
```
OriginalL'auteur Martin Andrews

Vous pouvez le faire en utilisant une approche de programmation dynamique appelé le Crible d'Eratosthène
Fondamentalement, vous créer un booléen cache de tous les nombres jusqu'à n et vous marquer tous les multiples de chaque numéro de not_prime.
D'autres optimisations peuvent être obtenus en vérifiant uniquement jusqu'à sqrt(n) puisque tout nombre composé auront au moins un diviseur moins que sqrt(n)

    public int countPrimes(int n) {
    if(n==0){
        return 0;
    }else{
        boolean[] isPrime=new boolean[n];
        for(int i=2;i<n;i++){
            isPrime[i]=true;
        }

        /* Using i*i<n instead of i<Math.sqrt(n)
         to avoid the exepnsive sqrt operation */
        for(int i=2;i*i<n;i++){
           if(!isPrime[i]){
               continue;
           }
            for(int j=i*i;j<n;j+=i){
                isPrime[j]=false;
            }
        }

        int counter=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                counter++;
            }
        }

        return counter;

    }
}

OriginalL'auteur Mad Scientist

C'est ce que j'ai développé pour Seive d'Eratosthène. Il y aurait de meilleures implémentations,bien sûr.

//trouve nombre de nombres premiers inférieurs à la longueur

private static int findNumberOfPrimes(int length) {
    int numberOfPrimes = 1;
    if (length == 2) {
        return 1;
    }

    int[] arr = new int[length];
    //creating an array of numbers less than 'length'
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i + 1;
    }
    //starting with first prime number 2, all the numbers divisible by 2(and upcoming) is replaced with -1
    for (int i = 2; i < arr.length && arr[i] != -1; i++) {

        for (int j = i; j < arr.length; j++) {
            if (arr[j] % arr[i] == 0) {
                arr[j] = -1;
                numberOfPrimes += 1;
            }
        }

    }
    return numberOfPrimes;
}

OriginalL'auteur Vikash

0

Le Crible d'Atkin est aussi le meilleur algorithme à mettre en œuvre dans ce cas et cela prend seulement O(N) opérations et O(N) l'espace. Veuillez vous référer https://en.wikipedia.org/wiki/Sieve_of_Atkin pour une explication détaillée de l'algorithme et de pseudo-code.

OriginalL'auteur Krish Bhanushali

Vous devez vous connecter pour publier un commentaire.