Nombres premiers C++ [Résolu/Fermé]

Signaler
-
 Utilisateur anonyme -
Bonsoir,

J'ai crée un algorithme affichant tous les nombres premiers de 1 à n.
Cependant, j'aimerais qu'il soit beaucoup plus rapide, auriez-vous des suggestions à me faire ?
J'ai entendu parler de la formule de Dana Jacobsen etc., quelqu'un pourrait-il m'éclairer ?
Actuellement, l'algo analyse 20.000 nombres en 1,2 secondes.

Voici le code :

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    double n;
    int k(0);
    int p(20000);
    bool test(true);
    //cout << "Jusqu'a quel nombre voulez vous afficher les nombres premiers ?" << endl;
    //cin >> p;
for(n = 2; n <= p; n++)
{
    test = true;
        for(int j = 2; j <= floor(sqrt(n)); j++)
        {
                double a = n/j;
                double b = floor(n/j);
            if(a == b)
            {
                test = false;
                break;
            }
        }
        if(test == true)
        {
        cout << n << "  ";
        k += 1;
        }
}
cout << endl << endl;
cout << "Parmi les " << p << " premiers nombre, " << k << " sont premiers." << endl;
    return 0;
}


Et voici un exemple :



Merci,
Cordialement, EchoIsON.
A voir également:

1 réponse

Messages postés
6553
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
23 octobre 2020
431
Bonjour,

Je ne connais pas la méthode de Dana Jacobsen, mais en général ces méthodes sont approximatives (ça l'est encore plus avec un ordinateur, car un ordinateur ne sait pas compter en nombre réel).

En ce qui concerne votre algorithme, plusieurs choses :
- Vous testez les nombres pairs. Les nombres pairs sont toujours non-premiers car ils sont tous divisibles par 2.
- Votre boucle va re-calculer la racine carrée de n à chaque fois.
- Vous utilisez cout dans la boucle. C'est l'opération la plus lente du programme.
- Vous n'utilisez pas l'opérateur de reste de division entière (%).
- Et vous n'utilisez qu'un seul cœur de votre processeur.

Voici le code que je vous propose, il utilise le c++11 et vient à bout de 20000 nombres en 0 seconde (2500 µs) sur une machine n'ayant qu'un processeur.
Imaginez si vous l'utilisez sur votre machine multi-processeurs ...

Vous pouvez le tester sur ce site : http://cpp.sh/5vfw

#include <iostream> // cout, cin
#include <cmath>    // floor, sqrt
#include <thread>   // thread, hardware_concurrency
#include <atomic>   // atomic
#include <vector>   // vector
#include <chrono>   // steady_clock

typedef unsigned int base_int;

using namespace std;

inline bool IsOdd(base_int const n) // Répond vrai si n est impair
{
	return (n & 1) == 1;
}

inline bool IsPrime(base_int const n) // Répond vrai si n est premier
{
	base_int const fs = floor(sqrt(n)); // Vaut mieux éviter de le re-calculer à chaque fois
	for(base_int k = 2; k <= fs; ++k)
		if(n % k == 0) return false; // % est l'opérateur qui donne le reste de la divison entière. Si le reste est 0, alors n est divisible par k donc n n'est pas premier.
	return true;
}

int main()
{
	atomic<base_int> thread_count(thread::hardware_concurrency());
	atomic<base_int> prime_count(0);
	base_int n;
	
	/*
		Chaque thread va s'occuper de tester des nombres uniquement impairs. On a donc besoin d'un nombre de threads pair, voir la suite.
	*/
	if(IsOdd(thread_count)) --thread_count;
	if(thread_count == 0) thread_count = 2; // On sera un peu plus lent sur les monoprocesseurs ... tant pis.
	
	vector<thread> thread_pool;
	thread_pool.reserve(thread_count);
	
	cout << "Jusqu'a quel nombre voulez vous afficher les nombres premiers ?" << endl;
	cin >> n;
	
	chrono::steady_clock::time_point tp_start = chrono::steady_clock::now();
	
	if(n > 1)
	{
		cout << "2" << endl;
		++prime_count;
		
		for(base_int start = 3, t = 0;
			t < thread_count;
			start += 2, ++t)
			{
				thread_pool.push_back(
					thread([=, &thread_count, &prime_count]()
						{
							
							for(
								base_int a = start; // On commence sur un nombre impair
								a <= n;
								a += thread_count
								/* 
									On reste sur des nombres impairs car les nombres pairs sont divisibles par 2 et sont donc toujours premiers. thread_count est pair.
								*/
								)
							{
								if(IsPrime(a)) 
								{
									++prime_count;
									//cout << n << endl; // Attention : cout est une opération blocante et afficher du text pendant l'opération va sérieusement ralentir le programme. De plus, on utilise des threads et celà va mélanger tout le texte.
								}
							}
							
						}
					)
				);
			}
	}
	
	for(thread & n : thread_pool) n.join();
	thread_pool.clear();
	
	chrono::steady_clock::time_point tp_end = chrono::steady_clock::now();
	
	cout << "Parmi les " << n << " premiers nombre, " << prime_count << " sont premiers (Resultat donne avec " << thread_count << " threads pour " << thread::hardware_concurrency() << " processeurs logiques en " << chrono::duration_cast<chrono::microseconds>(tp_end - tp_start).count() << " microsecondes, soit " << chrono::duration_cast<chrono::seconds>(tp_end - tp_start).count() << " secondes)." << endl;
	
	// pause
	int p;
	cin >> p;
	return 0;
}

1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

Messages postés
6553
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
23 octobre 2020
431 > Utilisateur anonyme
Je ne sais pas comment ne pas calculer la racine de n a chaque fois, pour moi il faut la recalculer toujours vu que n change à chaque tour.

La racine carrée sera aussi calculée à chaque fois que j change. C'est pour ça qu'il faut fixer la valeur avant d'entrer dans la boucle j.

Je me suis dit que ce serait plus rapide si j'inscrivais tous les nombres d'abord dans un tableau, pour ensuite les afficher

Ce qui prend du temps maintenant c'est
premier.push_back(n);

Il faut réserver le vector avant avec reserve.
celà va réduire le temps d'allocation dynamique de la mémoire.

Edit: il faut télécharger la version mingw de code::blocks
Bonjour.
Corrections faites, le programme met 0,016s pour analyser les 20.000 premiers sans les afficher.
Avec l'affichage, c'est 1,4s, c'est donc l'affichage qui prend beaucoup de temps ?
Lorsque je decide de les inscrire dans un fichier texte sans les afficher dans la console, le processus est presque isntantanné.

Je vais telecharger version mingw de code::blocks merci.

Edit :
Voici le code actuel


#include <vector>
#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

int main()
{
    int n;
    int k(1);
    int p(20000);
    bool test(true);
    //cout << "Jusqu'a quel nombre voulez vous afficher les nombres premiers ?" << endl;
    //cin >> p;

    vector<int> premier(1, 2);
    premier.reserve(p);
for(n = 3; n <= p; n+=2)
{
    test = true;
    double fs = floor(sqrt(n));
        for(int j = 2; j <= fs; j++)
        {
            if(n % j == 0)
            {
                test = false;
                break;
            }
        }
        if(test)
        {
        premier.push_back(n);
        k += 1;
        }
}

for(int i = 0; i < premier.size(); i++)
{
    cout << premier[i] << "\n";
}
cout << endl << endl;
cout << "Parmi les " << p << " premiers nombre, " << k << " sont premiers." << endl;
    return 0;
}


A mon avis, c'est le dernier for qui prend le plus de temps...

Edit : Code::Blocks migw telechargé, le code fonctionne avec 0 erreur.
Le programme est tres rapide, cependant les nombres sont affichés dans le désordre, par exemple :
2
7
5
3
etc.
Resultat donné avec 4 thread pour 4 processeurs logiques en 15600 microseconde
Voici le code : http://cpp.sh/77xi
Je trouve qu'il fonctionne plus vite sur C++Shell que sur Code::Blocks...
Par exemple le resultat pour p = 1.000.000 est instantanné
Messages postés
6553
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
23 octobre 2020
431 > Utilisateur anonyme
Le cout est effectivement le truc qui prend le plus de temps, je l'ai dit dans mon premier message. Imagine tout ce qu'il doit faire pour afficher un caractère à l'écran ...
Sur c++shell, à mon avis il ne doit pas s'occuper de l'affichage, le programme doit être redirigé directement vers le serveur web donc il est un peu plus rapide.

C'est normal que ce soit dans le désordre.
Lorsqu'on utilise des threads, il n'y a aucune garantie de la consistance de l'ordre du résultat puisque si on se mettait à faire attendre un thread pour avoir les résultats dans l'ordre, ils seront bloqués et les threads ne serviront plus à rien.

Si tu veux le résultat dans l'ordre, il faut créer un autre programme qui va se charger de trier le fichier où tu mets les résultats.

Il faut aussi compiler le programme en mode release et non en debug.
Utilisateur anonyme
Merci pour toute votre aide, je prend en compte vos conseils, merci egalement pour le code.
Je considere que le sujet est resolu.

EchoIsON