Dans un programme C, comment extrait-on des nombres premiers d'une suite de Fibonacci ?

Version imprimable

Mon examen universitaire comportait une question sur la génération de la série FIB et l'extraction des nombres PRIME du résultat. J'ai écrit le code suivant et j'obtiens le bon résultat. Cependant, je suis sûr que mon code n'est pas propre. Quelqu'un peut-il m'aider à écrire un nouveau code ou à modifier le mien et à le rendre propre ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
 
int main()
{
    int t1 = 0, t2 = 1, nextTerm = 0, n, i, position = 2, primeNumber[10], init = 2, count = 0;
    printf("Input N= ");
    scanf("%d", &n);
 
    printf("Fibonacci List: %d %d ", t1, t2);
    nextTerm = t1 + t2;
 
    while (nextTerm <= n)
    {
        printf("%d ", nextTerm);
        primeNumber[position] = nextTerm;
        position++;
        t1 = t2;
        t2 = nextTerm;
        nextTerm = t1 + t2;
    }
 
    printf("\nPrime numbers are ");
    position = 3;
    i = 1;
    init = 0;
 
    for (init = 1; init <= 7; init++)
    {
        for (i = 1; i <= primeNumber[position]; i++)
        {
            if (primeNumber[position] % i == 0)
            {
                count++;
            }
        }
        if (count == 2)
        {
            printf("%d ", primeNumber[position]);
        }
        count = 0;
        position++;
    }
    return 0;
}

Bonjour

Déjà première question: pourquoi le compteur des premiers va jusqu'à 7??? J'ai modifié ton code pour pouvoir afficher les 10000 premiers Fib et à chaque fois j'avais 2, 3, 5, 7, 11 !!!
Ensuite pourquoi mettre count à 0 alors que tu ne l'utilises plus? Un code propre ce n'est pas un code dans lequel on met tout à 0 une fois qu'on a fini. C'est un code facile à lire, facile à maintenir, facile à faire évoluer. Tu veux rendre ton code plus propre: faut le rendre plus modulable. Avec
une fonction dédiée qui calcule les n premiers Fibonacci
une fonction dédiée qui vérifie si un nombre est premier. Et déjà pour ça on peut aussi réfléchir un minimum. Parce que pour savoir si 391 est premier, je n'ai pas besoin de boucler jusqu'à 390. Une boucle jusqu'à 20 suffit !!! Ben oui, si je trouve n tel que 391/n = p avec n > p ça veut dire que je trouverai p bien avant tel que 391/p = n. C'est ça réfléchir avant de coder !!!
De plus, si on élimine directement 2 et les pairs, on peut alors se contenter ensuite de tester les impairs. Et là seulement 10 tests. C'est quand-même mieux que 390...:?
Donc une boucle sur i partant de 3 et allant de 2 en 2. Si (n % i) == 0 alors pas premier puis si (n / i) < i alors premier et terminé.

Ensuite il y a les petits plus. Comme par exemple allouer de la mémoire pour pouvoir stocker N Fibonacci une fois N saisi, travailler en unsigned quand c'est possible, mettre du const, etc...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <stdio.h> #include <stdlib.h> int isPrime(const size_t n) { if (n <= 1) return 0; if (n == 2 || n == 3) return 1; if (n%2 == 0) return 0; size_t i=3; while (1) { if (n%i == 0) return 0; if (n/i < i) return 1; i+=2; } } size_t* fibonacci(const size_t n) { size_t* fib=malloc(n * sizeof(*fib)); if (fib == NULL) { fprintf(stderr, "Erreur allocation %lu\n", n * sizeof(*fib)); return NULL; } fib[0]=1; fib[1]=1; size_t i=1; while (fib[i] <= n) { i++; fib[i]=fib[i-2] + fib[i-1]; } fib[i]=0; return fib; } int main() { size_t n; printf("Input N= "); scanf("%lu", &n); size_t* fib=fibonacci(n); if (fib == NULL) { fprintf(stderr, "Erreur fibonacci(%lu)\n", n); return -1; } // Affichage fibonacci for (size_t* pt=fib; *pt != 0; pt++) printf("%lu ", *pt); fputc('\n', stdout); // Affichage premiers size_t count=0; for (size_t* pt=fib; *pt != 0; pt++) { if (isPrime(*pt)) { count+=1; printf("%lu ", *pt); } } printf("- Total %lu premiers\n", count); free(fib); return 0; }
C'est pas le meilleur (perte de place parce que si N=50 j'alloue de la place pour 50 nombres mais en réalité je n'en stocke que 9: 1 1 2 3 5 8 13 21 34 <plus le 0 sentinelle donc en réalité 10>) mais déjà ça ressemble quand-même plus à quelque chose d'un peu pro...

Sinon concernant tes autres topics, ce serait poli d'y apporter des remarques aux réponses qu'on t'a fait, histoire qu'on ne se dise pas qu'on te répond pour rien...:?

Pour tester si c'est 1 nombre premier, il y a cette page Introduction to Primality Test and School Method, lien geeksforgeeks.org en anglais

Il y a 3 méthodes :

Méthode 1 : Tester de 2 à (n - 1) pour n > 1, sinon retourner faux
Code:

1 2 3 4 5 6 // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;
Méthode 2 : Tester de 2 à racine(n) pour n > 1, sinon retourner faux (je pense que c'est la méthode de @Sve@r)
Code:

1 2 3 4 5 6 // Check from 2 to square root of n for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true;
Méthode 3 : primality test, lien wikipedia en anglais
En gros, tous les nombres premiers au dessus de 3 sont de la forme (6k + 1) ou (6k - 1)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 bool isPrime(int n) { if (n == 2 || n == 3) return true; if (n <= 1 || n % 2 == 0 || n % 3 == 0) return false; // To check through all numbers of the form 6k ± 1 for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

25/01/2023, 19h56
Sve@r

Citation:

Envoyé par foetus

Méthode 2 : Tester de 2 à racine(n) pour n > 1, sinon retourner faux (je pense que c'est la méthode de @Sve@r)

Oui c'est celle-là puisque n/i devient plus petit que i quand i dépasse sqrt(n). Mais quelle que soit la méthode, on peut quand-même partir de 3 et ne tester que les impairs.

Citation:

Envoyé par foetus

En gros, tous les nombres premiers au dessus de 3 sont de la forme (6k + 1) ou (6k - 1)

Ca c'est intéressant !!! Et effectivement c'est vrai pour tous les nombres que j'ai testés entre 5 et 1000000... :applo:
Mais l'inverse n'est pas vrai. Un nombre 6k+1 ou 6k-1 n'est pas forcément premier...
30/01/2023, 14h18
jesse100

Merci à tous pour votre aide précieuse et votre temps:D
30/01/2023, 14h20
jesse100

Citation:

Envoyé par Sve@r

Bonjour

Déjà première question: pourquoi le compteur des premiers va jusqu'à 7??? J'ai modifié ton code pour pouvoir afficher les 10000 premiers Fib et à chaque fois j'avais 2, 3, 5, 7, 11 !!!
Ensuite pourquoi mettre count à 0 alors que tu ne l'utilises plus? Un code propre ce n'est pas un code dans lequel on met tout à 0 une fois qu'on a fini. C'est un code facile à lire, facile à maintenir, facile à faire évoluer. Tu veux rendre ton code plus propre: faut le rendre plus modulable.

[…]

C'est pas le meilleur (perte de place parce que si N=50 j'alloue de la place pour 50 nombres mais en réalité je n'en stocke que 9: 1 1 2 3 5 8 13 21 34 <plus le 0 sentinelle donc en réalité 10>) mais déjà ça ressemble quand-même plus à quelque chose d'un peu pro...

Sinon concernant tes autres topics, ce serait poli d'y apporter des remarques aux réponses qu'on t'a fait, histoire qu'on ne se dise pas qu'on te répond pour rien...:?

Oui, merci beaucoup