Bonjour.

J'ai créer un petit programme en C affichant le nombre premier le plus grand avant un nombre entré par l'utilisateur.

Voici mon problème : je trouve que le programme est trop lent, que puis-je faire pour qu'il aille beaucoup plus vite ?
Actuellement il vient à bout de 20.000 nombres en 0.020s, 200.000 en 0.039s et 2.000.000 en 0.671s.

Voici un exemple :

1999993

Parmi les 2000000 premiers nombres, 148933 sont premiers.

Process returned 0 (0x0)   execution time : 0.671 s

Press any key to continue.

Voici le code :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef enum
{False = 0, True = 1}
Bool;

int main()
{
    int n, la;
    int k = 1;
    int p = 2000000;
    Bool test = True;

for(n = 3; n <= p; n+=2)
{
    test = True;
    double fs = floor(sqrt(n));
    int j;
        for(j = 2; j <= fs; j++)
        {
            if(n % j == 0)
            {
                test = False;
                break;
            }
        }
        if(test)
        {
        //printf("%d\n", n);
        k += 1;
        la = n;
        }
}
    printf("%d\n", la);
    printf("\nParmi les %d premiers nombres, %d sont premiers.\n", p, k);
    return 0;
}

Merci pour votre aide.
 

Bonjour,

le problème est que tu utilises un algorithme qui sert à tester si un nombre est premier pour écrire un algorithme qui trouve le nombre de "nombres premiers" dans un certain intervalle.

le 1er algorithme simple à écrire qui permet d'optimiser est celui d'erasthotene.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef enum
{
	False = 0 , True = 1
} Bool;

const int p = 20000000;
Bool arr[p] = { False };

int main() {
	int k = 0;
	for ( int i = 2 ; i < p ; ++i ) {
		if ( !arr[i] ) {
			for ( int m = i<<1 ; m < p ; m += i ) {
				arr[m] = True; // 
			}
			++k;
		}
	}
	printf( "\nParmi les %d premiers nombres, %d sont premiers.\n" , p , k );
	return 0;
}

Dalfab,

Merci pour cet exemple.

Voici les nouveaux tests :

20.000 nombres en 0.027s

200.000 nombres en 0.041s

2.000.000 nombres en 0.070s

La différence ne se marque pas trop pour les petits nombres mais elle est bien réelle pour des nombres plus grands, je suis à 0.676s pour 20.000.000 de nombres.

Pourriez-vous, si cela n'est pas trop demander, m'expliquer le code avec des commentaires ? Et pourquoi est-ce-qu'on utilise des tableaux pour le booléan arr ? Est-ce obligatoire ?

Encore merci. 

Hello,

Oui, le tableau arr[] est nécessaire, il permet de ne pas refaire un job déjà effectué: éliminer les multiples de 9 alors que les multiples de 3 ont déjà été éliminés (exemple).

La ligne 16 permet de savoir si le nombre a été éliminé. Si ce n'est pas la cas, le programme supprime tous ses multiples (ligne 17 à 20), et k (le nombre de nombre premier trouvés) est incrémenté (ligne 21).

Le for() ligne 17 à 20 met à True, à partir de arr[i*2] (m=i<<2 signifie m=i*2), tous les multiples de i.

A+

Edgar;

-
Edité par edgarjacobs 18 mars 2016 à 23:02:16