# Projet LEPL1503 - Prime factorization "Prime factorization" est un programme écrit en langage C. Il prend en entrée un fichier texte de nombres et renvoie un nouveau fichier texte avec, à chaque ligne, le nombre à factoriser et la liste de ses diviseurs premiers. Le programme fonctionne en "muli-threading" et le nombre de threads est paramétrable. ## Objectif du projet Convertir et optimiser un programme python en langage C et retourner les diviseurs premiers de chaque entier d'une liste de nombres. ## Fichiers * **Makefile** : Permet l'exécution de commandes (compilation du code, exécution des tests). * **run.c** : Contient le corps du code de l'algorithme * **run.h** : Contient les signatures des fonctions de run.c. * **main.c** : Contient la fonction main du programme principal (run.c). * **test.c** : Contient des tests en CUnit permettant de tester les fonctions de run.c. * **Test_files** : Dossier contenant différents input et output pour divers exemples de nombres (entiers,petits,grands). ## Librairies utilisées - Librairies standards en C - Librairie pthreads et semaphores: exécution des threads et des semaphores - Librairie Cunit: utilisée pour les tests unitaires - Librairie time: calcule le temps d'exécution du programme ## Installation Les packages suivants doivent être installés : * [CUnit](https://sites.uclouvain.be/SystInfo/notes/Outils/html/cunit.html) * Valgrind : sudo apt-get install valgrind * Cppcheck : sudo apt-get install cppcheck ## Utilisation * Pour compiler le programme : make fact * Pour exécuter le fichier exécutable "fact" : ./fact [-N nombre_de_threads] input output * Pour compiler et tester (suite de tests unitaires) le programme : make test * Pour compiler et effectuer une analyse avec "Valgrind" : make val * Pour compiler, et obtenir le rapport d'analyse .xml de "Valgrind" : make val_xml * Pour effectuer une analyse avec "cppcheck" : make cpp * Pour compiler et obtenir le rapport d'analyse .xml de "cppcheck" : make cpp_xml * Pour nettoyer les fichiers auxiliaires générés et l'exécutable : make clean ## Architecture du programme: Le travail est décomposé en 3 sections coordonnées via un double problème du producteur-consommateur : * 1 thread s'occupe de: * lire le fichier input * stocker chacune des lignes sous forme de chaine de charactère dans un 1er tableau * N threads s'occupent de : * récupérer les chaines de caractères dans le premier tableau * les convertir en 'unsigned long long' et calculer leur liste de diviseurs premiers grâce au test de primalité de Fermat * Stocker ces listes dans un 2e tableau * 1 thread s'occupe de : * récupérer les listes de diviseurs dans le 2e tableau * Retranscrire dans le bon format le nombre à factoriser et ses diviseurs premiers dans le fichier output Note : * Les accès aux tableaux sont coordonnés par des mutex (1 par tableau) et des sémaphores * Les diviseurs premiers d'un même nombre sont stockés dans une circular linked list * Le nombre de threads de calcul par défaut est 8 ## Architecture des tests : 10 tests sont réalisés afin de vérifier: * "is_div" (2 tests) * "is_prime" (2 tests) * "mod_pow" * "randomiser" * Le fonctionnement complet pour un fichier vide (N = 4) * Le fonctionnement complet pour un fichier d'une ligne : check du format et des diviseurs (N = 4) * Le fonctionnement complet pour un fichier de 100 lignes : check du nombre de lignes (réalisé avec N = 4 puis N = 1) # lepl1503-2020-groupe-M2