nombres premiers

Factorisation première #

Exemple d’implémentation d’un algorithme de factorisation en nombres premiers. Un algorithme de factorisation trouvera pour un nombre donné n une liste de nombres premiers, de sorte que si vous multipliez ces nombres premiers, vous obtenez n. L’implémentation ci-dessous ajoutera -1 à la liste des facteurs premiers dans le cas n < 0. Notez qu’il n’existe pas de factorisation première de ‘0’, donc la méthode ci-dessous renvoie une liste vide.

List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    if (n < 0) {
        factors.add(-1);
        n *= -1;
    }
    for (int i = 2; i <= n / i; ++i) {
        while (n % i == 0) {
            factors.add(i);
            n /= i ;
        }
    }
    if (n > 1) {
        factors.add(n);
    }
    return factors ;
}

Premier contrôle #

Veuillez noter que par définition, “1” n’est pas un nombre premier. Pour vérifier si un nombre n est un nombre premier, nous devrions essayer de trouver un diviseur i de n. Si nous ne pouvons pas, alors n est un nombre premier. Nous avons trouvé un diviseur lorsque n % i == 0 est évalué à vrai. Nous n’avons qu’à essayer les nombres impairs, puisqu’il n’y a qu’un seul nombre premier pair, à savoir 2, que nous traiterons comme un cas particulier. De plus, seuls les nombres jusqu’à et y compris sqrt(n) sont des diviseurs possibles, car lorsque n = a * b alors au moins un des facteurs est au plus sqrt(n).

Pour vérifier si un nombre est un nombre premier ou non, l’algorithme suivant peut être utilisé :

boolean isPrime (int n) {
    if (n < 2) {
        return false;
    }
    if (n % 2 == 0) {
        return n == 2;
    }
    for (int i = 3; i*i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true ;
}

Premier tamis #

Le tamis d’Ératosthène génère tous les nombres premiers de 2 à un nombre donné n.

1. Supposons que tous les nombres (de 2 à n) sont premiers.
2. Ensuite, prenez le premier nombre premier et supprimez tous ses multiples.
3. Répétez l’étape 2 pour le prochain premier. Continuez jusqu’à ce que tous les chiffres jusqu’à n aient été marqués.

Pseudo-code :

Input: integer n > 1
 
Let A be an array of Boolean values, indexed by integers 1 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., not exceeding sqrt(n):
    if A[i] is true:
        for j = 2i, 3i, 4i, 5i, ..., not exceeding n :
            A[j] := false
 
Output: all i such that A[i] is true.

Code C :

void PrimeSieve(int n)
{
    int *prime;
    prime = malloc(n * sizeof(int));
        int i;
        for (i = 2; i <= n; i++)
            prime[i] = 1;    
    
       
    int p;
    for (p = 2; p * p <= n; p++)
    {    
        if (prime[p] == 1) // a Prime found
        {
            // mark all multiples of p as not prime.
            for (int i = p * 2; i <= n; i += p)
                prime[i] = 0;
        }
    }
 
    // print prime numbers
    for (p = 2; p <= n; p++)
        if (prime[p] == 1)
            printf("%d ", p);
}