Nombres premiers C++

Résolu/Fermé
Utilisateur anonyme - 29 janv. 2016 à 23:14
 Utilisateur anonyme - 31 janv. 2016 à 22:21
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

SypayV
Messages postés
6554
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
27 juin 2021
453
30 janv. 2016 à 08:29
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
Utilisateur anonyme
30 janv. 2016 à 18:34
Bonsoir.

Merci beaucoup pour tout cela, j'ai quand meme quelques questions...
Code::Blocks ne prend pas en charge les fonctionnalites C++11 ?
De plus, sur C++Shell, le programme ne m'affiche pas tous les nombres, seulement un "2" quand je rentre 20000 par exemple...

Mais sinon, j'ai a peu pres compris le code, meme s'il y a beaucoup de fonctions que je ne connais pas... Merci encore.


EchoIsON.
0
SypayV
Messages postés
6554
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
27 juin 2021
453 > Utilisateur anonyme
Modifié par SypayV le 30/01/2016 à 20:50
Code::Blocks supporte le C++11 normalement.
Voici comment l'activer : https://stackoverflow.com/questions/18174988/how-can-i-add-c11-support-to-codeblocks-compiler/24398366#24398366

J'ai commenté la partie du code qui affiche les nombres car si on l'active alors le programme va ralentir et le texte sera désordonné car le code est parallèle.
Exemple : http://cpp.sh/673b4

Il faut créer un autre thread qui devra s'occuper d'afficher le texte.
Mais il sera rapidement dépassé, c'est à dire que les calculs seront finis avant même qu'il ait fini d'afficher tout le texte ... donc la meilleure solution est d'enregistrer les nombres et de les afficher à la fin du programme.
Exemple : http://cpp.sh/52gt

Cependant, le voilà déjà 2 fois moins rapide.

Le 2 est affiché à l'avance car sinon ce serait la misère avec les threads, pour leur dire de compter uniquement des impairs. Il y a un thread qui commence à 3, l'autre commence à 5, l'autre commence à 7, ainsi de suite ... Et ensuite ils passent respectivement à 3+nombre_de_theads, 5+nombre_de_theads, etc ... Chaque thread à sa propre échelle de nombre à calculer, nombre_de_threads étant toujours pair : pair+impair=impair.

Si tu veux en apprendre plus sur le code fourni, cherches avec google sur :
Multithread, opérations atomiques, c++11 fonctions lambda et pour le reste vois avec la documentation https://fr.cppreference.com/w/cpp

Edit : Je viens de me rendre compte que j'ai fait une erreur.

Pour que chaque thread ait sa propre échelle, il faut incrémenter de 2*nombre_de_threads ...et pas seulement une fois;
http://cpp.sh/25sp
Voilà, on est devenu 2 fois plus rapide sur le site. Ce sera encore 4 fois plus rapide que ça sur un quad core.
0
Merci, j'ai testé le code sur C++Shell, il marche bien, sauf que sur Code::Blocks, le compilateur me renvoie une tonne d'erreurs... Comme :

||=== Build: Debug in supprapres (compiler: GNU GCC Compiler) ===|
C:\Users\main.cpp||In function 'int main()':|
C:\Users\main.cpp|29|error: 'thread' has not been declared|
C:\Users\main.cpp|32|error: 'mutex' is not a member of 'std'|
C:\Users\main.cpp|32|error: expected ';' before 'prime_pool_mtx'|
C:\Users\main.cpp|41|error: 'thread' was not declared in this scope|
C:\Users\main.cpp|41|error: template argument 1 is invalid|
C:\Users\main.cpp|41|error: template argument 2 is invalid|
C:\Users\main.cpp|41|error: invalid type in declaration before ';' token|
C:\Users\main.cpp|42|error: request for member 'reserve' in 'thread_pool', which is of non-class type 'int'|
C:\Users\main.cpp|60|error: request for member 'push_back' in 'thread_pool', which is of non-class type 'int'|
C:\Users\main.cpp|61|error: 'prime_pool_mtx' was not declared in this scope|
C:\Users\main.cpp|78|error: 'lock_guard' was not declared in this scope|
C:\Users\main.cpp|78|error: 'mutex' is not a member of 'std'|
C:\Users\main.cpp|78|error: 'lck' was not declared in this scope|
C:\Users\main.cpp||In function 'int main()':|
C:\Users\main.cpp|90|error: found ':' in nested-name-specifier, expected '::'|
C:\Users\main.cpp|90|error: 'z' has not been declared|
C:\Users\main.cpp|90|error: expected ';' before ')' token|
C:\Users\main.cpp|91|error: request for member 'clear' in 'thread_pool', which is of non-class type 'int'|
C:\Users\main.cpp|93|error: expected primary-expression before 'for'|
C:\Users\main.cpp|93|error: expected ')' before 'for'|
C:\Users\main.cpp|97|error: 'thread' is not a class, namespace, or enumeration|
||=== Build failed: 20 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|


Un probleme de bibliotheques ?


Edit : de plus, je comprend en general le code, mais il y a certains passages que je ne comprend absolument pas... Comme celui la :

atomic<base_int> thread_count(thread::hardware_concurrency());
	atomic<base_int> prime_count(0);
	vector<base_int> prime_pool;
	std::mutex prime_pool_mtx;
	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();
	
	prime_pool.reserve(n);


ou encore cette ligne :
thread([=, &thread_count, &prime_count, &prime_pool, &prime_pool_mtx]()


Et ces deux for :

for(thread & z : thread_pool) z.join();
	thread_pool.clear();
	
	for(base_int x : prime_pool) cout << x << endl;


Je ne vois pas leur rapport avec le calcul des nombres premiers...

Merci.

EchoIsON
0
SypayV
Messages postés
6554
Date d'inscription
vendredi 28 décembre 2007
Statut
Contributeur
Dernière intervention
27 juin 2021
453 > Utilisateur anonyme
30 janv. 2016 à 23:20
Tu n'as pas activé c++11 sur Code::Blocks.
https://mementolinux.wordpress.com/2012/11/14/utiliser-c11-avec-codeblocks-sur-windows/

Tu comprendras le code si tu prends le temps de te documenter avec les recherches google.

Les deux for dont des for qu'on peut utiliser avec le c++11.
Le premier for prend chaque valeur du vector par référence (pour pouvoir modifier).
Le deuxième prend chaque valeur du vector par copie (Pour pouvoir afficher les nombres).
0
Utilisateur anonyme
31 janv. 2016 à 00:16
J'ai deja ete sur ce site... Je n'arrive pas a telecharger mingw ni en x32 ni en x64, lorsque je telecharge le build d'un autre site, le compilateur Code::blocks ne reconnait pas, et ne compile rien...
Je regarderai pour le code.

Sinon, j'ai essayé de modifier le mien un peu, en suivant vos conseils, mais le temps d'execution est le meme...

#include <vector>
#include <iostream>
#include <cmath>
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);
for(n = 3; n <= p; n+=2)
{
    test = true;
        for(int j = 2; j <= floor(sqrt(n)); j++)
        {
            if(n % j == 0)
            {
                test = false;
                break;
            }
        }
        if(test == true)
        {
        premier.push_back(n);
        k += 1;
        }
}
for(int i = 0; i < premier.size(); i++)
{
    cout << premier[i] << endl;
}
cout << endl << endl;
cout << "Parmi les " << p << " premiers nombre, " << k << " sont premiers." << endl;
    return 0;
}


Je me suis dit que ce serait plus rapide si j'inscrivais tous les nombres d'abord dans un tableau, pour ensuite les afficher... A moins que je ne me soit trompé.
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.

Merci
EchoIsON
0